## Microsoft Interview Question

• 0

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

Here is my answer to the question:

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

Comment hidden because of low score. Click to expand.
0

It will fail in one scenario.
Consider a tree
a
/ \
a b
/
a
/ \
d e
and,

a
/
a
/ \
d e
yoursandmyideas.wordpress.com

Comment hidden because of low score. Click to expand.
0

/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
bool areIdentical(struct node * root1, struct node *root2)
{
/* base cases */
if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1->data == root2->data &&
areIdentical(root1->left, root2->left) &&
areIdentical(root1->right, root2->right) );
}

/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(struct node *T, struct node *S)
{
/* base cases */
if (S == NULL)
return true;

if (T == NULL)
return false;

/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;

/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T->left, S) ||
isSubtree(T->right, S);
}

Comment hidden because of low score. Click to expand.
0
of 2 vote

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);

}

Comment hidden because of low score. Click to expand.
0

to check if T2 is a subtree of T1 you should start from
the *root node* of T2 while in

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

you just start from some interior node of T2

Comment hidden because of low score. Click to expand.
0

furthermore if T1 has millions of nodes and is not balanced you can easily run out of stack space, so I don't think that recursive alg is appropriate

Comment hidden because of low score. Click to expand.
0

i have started from root node of t2 only have look again ....

The second probable method would be

Store the inorder and preorder traversal of T1 in disk

And do the same for the T2

now start looking the match of T2's traversal over T1's traversal

Both traversal (inorder and preorder should match.

Comment hidden because of low score. Click to expand.
0

I think there is a quite subtle problem with matching in-order/post-order traversals because it might happen that even if there is a match, trees are different, e.g.:

``````T1 is:
a
/    \
f       c
/         \
c           f
/             \
e               e
in-order: ecfacfe
post-order: ecfefca

and  T2 is:
c
/  \
e   f
in-order: ecf
post-order: efc

hence  there is a match both for in- and post-order traversals but T2 is not a subtree of T1``````

Comment hidden because of low score. Click to expand.
0

What i meant is once u find the match construct the tree from those nodes ofT1 and if they match then return true otherwise return false

Comment hidden because of low score. Click to expand.
0

This is not guaranteed to work.

It is possible that T1 is created with different input set what you supply later after finding a subtree from T1 using preorder and inorder traversal.

E.g
T1 is

``````5
/
4
/     \
3      4
/
2``````

In order traversal = 2 3 4 4 5
Preorder traversal = 5 4 3 2 4

T2 is

``````3
/   \
2     4``````

In order traversal = 2 3 4
Preorder traversal = 3 2 4

Now if you construct a tree from the nodes of T1 (using 2, 3, 4), you would always get tree
as T2, but T2 is not really a subtree of T1.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

It will fail in one scenario.
Consider a tree
a
/ \
a b
/
a
/ \
d e
and,

a
/
a
/ \
d e

Comment hidden because of low score. Click to expand.
0

you don't consider duplicate case. when some node in T1 have same value in T2->root, it may failed for your code.

But your algorithm is wonder, just for a little revise it will work.

Comment hidden because of low score. Click to expand.
0

i think you algo is seems to correct...

Comment hidden because of low score. Click to expand.
0

sorry .. there is really one mistake.. otherwise it is fantastic algo..
you have to preserve the root of the T2 while it matched for some point and it did not match it.
it sould b like this
here T3=T2;
issubtree(struct node* T1,struct node* T2,struct node* T3)
{
if(T1==null)return false;
if(T2==null)return true;
if(T1->data==T2->data)
return issubtree(T1->left,T2->left,T3)&&issubtree(T1->right,T2->right,T3);
else
{
T2=T3;
return issubtree(T1->left,T2,T3) ||issubtree(T1->right,T2,T3);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.``````

.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Since nodes with duplicated values are allowed, you can easily construct a counter example...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is in their book

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

Only if T1 is balanced...

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.