Hi, I didn't understnad your answer.
Can you please give some example for it?
Thanks.

if the root of T2, let say r is unique in T1, then this problem becomes simple. But since there could be thousands of r in T1, so we cannot afford to check every sub tree rooted at those r's. My algorithm given above first locate the only possible candidate and then check it. which is describe again below:
find the predecessor(with a different value) of r in T2, let's denote it s, the same way, find the successor(with a different value) of r in T2, let's denote it b. Then if T2 is a subtree of T1, then s and b must appear in T1, so we search s and b in T1, although there might be hundreds of s or b in T1, but that doesn't matter, because duplicates huddle togethor. So if we find s and b in T1, no matter which copy we find, their least common ancestor in T1 should be the same, let's denote it a, then if T1 contains T2, a must equals r, and T2 must be identical to the subtree rooted at a in T1.

dude, this is a binary tree not a BST, so why would duplicates huddle together ?

I don't agree with you. Since T1 has millions of nodes, it is impoosible to store or print the full path.

find the string representation of T2 ("flatten"). use a special character to represent a missing child - in this way, it will be unique. traverse T1. the idea is to flatten T1 similar to that of T2, but in this case, retain only the last hundred characters (size of T2) of the string representation of T1. when u hit a match, then u got the answer.

since we are doing partial string match, it is possible that the representation of a set of leaf nodes + another subtree to be equal to T2, when its really not. so use some other special characters after every leaf node in our "flattening" scheme. In that way, the leaf nodes + other partial subtree will not be equal to T2. Hope its not confusing

I don't understand why T2 is not a subtree of T1. simply because it has no right subtree?

why are you writing the code? with out atlease giving a hint of what it is doing? Bcoz, even u dont know what it is doing right? see how dumb ppl are !

he is actually pretty clear. he is using a recursive method to check equality of nodes.

And there is something wrong with the code, the CheckNodes never returns true

also the CheckNodes is wrong as pointed by the return conditions here is what works. Also not sure if your functions handle cases when a tree T2 is bigger than a subtree T1 which match upto certain nodes
T1.
X
\
13
/ \
11 14

T2

13
/ \
11 14
\
15

My implementation uses a FindTreeNoePtr function and a LevelOrder checking. I will post the solution after the break.

//0. Assume Result is true by default then you setup cases where it fails
//1. If my current NodePtrs are null exit don't even check anything or you get memory corruption for obvious reasons
//2. If my NodePtrs Data and Duplicate cnts do not match then your subtree fails so your result = FALSE.
//3. If i did not have any data mismatches at this point, now I need to recursivly check my children but before that I need to do the following.
// a. Need to Check if T1 has the left child when T2 has the left child, and also similarly for the right child
// If T1's subtree is missing a child that T2 has then it is an automatic fails so you result = FALSE
//4. If you result is still true keep going and check the children left followed by right. Again here if your
// left child fails then exit out, no need to check the right.
//5. Finally return the result down the recursive function call stack till it is sent back to the caller.

bool CheckNodesTrees(TreeNode *NodePtrT1, TreeNode *NodePtrT2){
bool Result = true;

if((NodePtrT1!=0 && NodePtrT2!=0)){
if((NodePtrT1->Data!=NodePtrT2->Data)||
(NodePtrT1->Duplicates!=NodePtrT2->Duplicates)){
Result = false;
}
if(Result){
if((NodePtrT1->Left==0 && NodePtrT2->Left!=0)||(NodePtrT1->Right==0 && NodePtrT2->Right!=0)){
Result = false;
}
if(Result){
Result = CheckNodesTrees(NodePtrT1->Left,NodePtrT2->Left);
if(Result){
Result = CheckNodesTree(NodePtrT1->Right,NodePtrT2->Right);
}
}
}
}
return Result;
}

Forgot to mention, good recursive solution Swati other than the mistake above, more or less it works. good job.

bool evaluate(struct node * root, struct node * root2, bool found, struct node * original_root2)
{
if(root == NULL && root2 == NULL) return true;
if(root == NULL && root2 != NULL) return false;
if(root != NULL && root2 == NULL) return true;

if(root->data == root2->data)
{
return ( evaluate(root->lptr,root2->lptr,true,original_root2) && evaluate(root->rptr,root2->rptr,true,original_root2));
}
else if(root->data == original_root2->data)
{
return ( evaluate(root->lptr,original_root2->lptr,true,original_root2) && evaluate(root->rptr,original_root2->rptr,true,original_root2));
}
else if(found)
{
root2 = original_root2;
}
return (evaluate(root->lptr,root2,false,original_root2) || evaluate(root->rptr,root2,false,original_root2));
}

I don't understand your question ? if T2 < T1, how do you know this, other than acutally traversing the T1 with values of T2. That is what Swati's code above does, there are couple of cases she does not take into account which I pointed out.

I have a solution. If it is a repetition of one of the previous algos, please forgive.

1. Flatten T1, Flatten T2, (some traversal algo).
2. Now you have a big string and a small string.
3. Precompute skip array for the smaller string and do a string comparison. This is almost O(strlen(T2));

Step 3 is actually Knuth Morris Pratt algorithm. You can find it on Wikipedia.

Suggestions/comments/criticisms welcome.

Thanks,
Rohith Menon.

The previous post has an error, its O(strlen(T1)).

Sorry and thanks,
Rohith Menon.

Traversal algo should be such that it uniquely defines a tree. So inorder+pre/post.

maybe i missed something but if T2 is a SUBTREE of T1 then I guess we can just traverse the ancestors of root[T1] to reach[T2]

The linear data structure (string, list or array) obtained by visiting the tree in-order does not describe the tree unambiguously, i.e. two different trees can yield the same sequence.

But I think that the pair of sequences obtained from visiting in-order and then in pre-order uniquely describes the tree (the tree can be unambiguously reconstructed from the 2 sequences).