CareerCup

Here is my answer to the question:

basicalgos.blogspot.com/2012/03/29-issubtree.html

bool IsSubset(Node *T1, node *T2)
{
if(!T2)
return true;

if(!T1)
return false;


if(T1->data==T2->data)
return IsSubset(T1->left,T2->left)&&IsSubset(T1->right,T2->right);

else
return IsSubset(T1->left,T2)||IsSubset(T1->right,T2);

}

I think

The above algorithm/code should work. Because
In case of duplicates in Binary three, the implemetation may be increment-ing the count an any given node .
And Since it is char data type at max 256 different values will be in the binary tree. If there is duplicate increment the count in that node.

bool isSubtree(Node *T1, Node *T2)
{
if(T1 == NULL && T2 == NULL)
return true;
if(T2 == NULL)
return true;
bool boolean = T1-data == T2->data ? true : false;
if(isSubtree)
return boolean && isSubtree(T1->left, T2->left) && isSubtree(T1->right, T2->right);
else
{
return isSubtree(T1->left, T2) || isSubtree(T1->right, T2);
}
}

Do a preprocessing step of computing the size of the subtree rooted at any node in a given tree. The time complexity is O(n). Doing this for the tree to be searched and for the given tree would have O(n + m) complexity. In this case n >> m ( n is of the order of millions and m ,of the order of hundreds). So the numNode computation would actually be O(n)

Following is the algorithm ( t is the search tree, and k is the key tree)


boolean isSubtree(Tree * t , Tree * k){

if( k == null)
return true;

if( t ! = null && t-> num_nodes == k->num_nodes)
return isIdentical( t , k);

if( t->left != null && t->left->num_nodes >= k->num_nodes)
return isSubtree(t - > left, k);

if( t->right != null && t->right >num_nodes >= k->num_nodes)
return isSubtree(t - > right, k);

return false;

}



isIdentical(Tree * A, Tree * B){

if((A==null && B==null)){
return true;
}

if((A==null && B!=null) || (A!=null && B==null)){
return false;
}

if(A->value != B->value)
return false;

return isIdentical( A->left, B->left) && isIdentical( A->right, B->right);
}

NumNode computation time =O( n + m)

isIdentical computation = O(m) = const.

T(n) = 2T(n/2) + O (m) = 2T(n/2) + const.

Time complexity = O(n)


typedef struct Node Tree {
int value;
int num_nodes;
Tree * left:
Tree * right:
}

public static boolean isSubtree(Node main, Node subtree)
{
if (main == null && subtree == null)
{
return true;
}

if (main == null || subtree == null)
{
return false;
}

if (main.value == subtree.value)
{
boolean current = isSubtree(main.left, subtree.left) && isSubtree(main.right, subtree.right);

if (current)
{
return true;
}

}

return isSubtree(main.left, subtree) || isSubtree(main.right, subtree);
}

I think there is a easier way to do that. It says that the tree stores character data. So we can do a in/pre/post-order traversal for T1 and T2. Then, we will check the length of T2 and sees if it matches the same character and the same length of T1 depending of the traversal. For instance, if we have the tree :

T1 =  f                   and T2 =        h   
             /        \                                       /       \ 
           d         h                                    i         l
         /    \     /    \
        a    b   i      l

    in-order traversal of T1 = a d b f i h l   and of T2 = i h l
   
  We only have to check if T2 is a substring of T1 and since it's in-order traversal, we check only the last character of T1 that matches T2.

.

To avoid useless check we can calculate hash for each node during post-order traversal.
for ex, hash(T) = (T->data * hash(T->left) * hash(T->right)) % big_prime_number
With big probability if hash(T1) == hash(T2) then T1 == T2, and it's a true is hash(T1) != hash(T2) then T1 != T2 for sure.
So, only when hash(T1) == hash(T2) we should start naive checking algo.

I haven't tested this for all test cases, but we could:

1. Perform in-order, pre-order, post-order traversal on both trees.
2. Store each traversal in an array.
3. Find if T2 is a substring of all 3 traversal arrays. If so, then T2 is a subset of T1, else not. Even if one match fails, return false and exit.

I haven't tested this for all test cases, but we could:

1. Perform in-order, pre-order, post-order traversal on both trees.
2. Store each traversal in an array.
3. Find if T2 is a substring of all 3 traversal arrays. If so, then T2 is a subset of T1, else not. Even if one match fails, return false and exit.

bool isSubTree(tree *big, tree *small)
{
bool subsetFound = false;

if (big == NULL)
return false;
if(small == NULL)
return true;

if(big->data == small->data)
{
subsetFound = isMirrorSubset(big, small);
}

if(!subset)
return isSubTree(big->left, small) || isSubTree(big->right, small);

return true;
}


bool isMirrorSubset(tree *root1, tree *root2)
{
if(root1 == NULL || root2 == NULL)
return true;

if(root1->data == root2->data)
return (isMirrorSubset(root1->left, root2->left) && isMirrorSubset(root1->right, root2->right));
}

it is in their book

Alogo:
1) Find the height of both the trees.
2) Take the difference, this difference tells us to what level from root we can search for the root element of t2(smaller tree).
3) So inorder to avoid unwanted search of the smaller tree in the wrong subtree, we can do level wise search first for the root node of the smaller tree.
4) Once we get a match and its range where we can have the subtree then we can go searching for it.

For Example:
T1- height 10000
T2- height 2000

So we need to search till 8000 level from root to find the subtree.