Saturday, 17 August 2013

Is This Statement True (Used to Determine If a Tree is a SubTree of Another)

Is This Statement True (Used to Determine If a Tree is a SubTree of Another)

I have two binary trees T1 and T2, and they are both character trees,
which means:
struct TreeNode
{
char data;
TreeNode* left;
TreeNode* right;
TreeNode(const char d, TreeNode* const lptr = NULL,
TreeNode* const rptr = NULL)
: data(d), left(lptr), right(rptr){}
};
If PreOrder2 is a substring of PreOrder1, and InOrder2 is a substring of
InOrder1, then T2 is a subtree of T1.
Is the above statement true?
Definition of Tree Equal: if T1 and T2 have the exactly same data values
AND distribution, then T1 == T2, otherwise T1 != T2 (NULL trees are
equal).
Definition of SubTree: if there is at least one node N1 in T1 that N1 ==
T2, then T2 is a subtree of T1.
== EDIT ==
I think it's not true. It's possible that there are two subtrees in T1,
one of which has the same PreOrder as T2, the other has the same InOrder
as T2.
Now my question becomes: is there a simple way to determine if T2 is a
subtree of T1 using traversals?

No comments:

Post a Comment