Determine if given binary tree is a subtree of another binary tree or not

Given a binary tree, determine if it is a subtree of another binary tree or not. A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.


 
For example,
 
Subtree

second tree is subtree of the first tree
 


 

Naive solution would be check if every sub-tree rooted at every node in the first tree is identical to the second tree or not. The time complexity of this solution is O(MN) where N is the size of first tree and M is the size of the second tree.

 

We can solve this problem in linear time by using extra space. We know that inorder and pre-order traversal or inorder and post-order traversal identify a tree uniquely. The idea is store in-order and post-order traversal of both trees in separate arrays. Then, in order for a given binary tree X to be subset of another binary tree Y, the in-order traversal of X should be sub-set of in-order traversal of Y. Similarly, the post-order traversal of X should be sub-set of post-order traversal of Y. We can also perform pre-order traversal instead of post-order traversal. For example, consider above trees


inorder(X) = {4, 2, 5, 1, 6, 3, 7}
inorder(Y) = {6, 3, 7}
 

postorder(X) = {4, 5, 2, 6, 7, 3, 1}
postorder(Y) = {6, 7, 3}
 

Since, inorder(Y) is subset of inorder(X) and postorder(Y) is subset of postorder(X), we can say that Y is sub-tree of X.

 
C++ implementation –
 
 

Download   Run Complete Code

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Avishek Dutta
Guest
Avishek Dutta

The complexity is O(n*m) [complexity of search] where n is the length of the tree vector and m is the length of the subtree vector. In worst case n==m then time complexity becomes O(n^2).

Refer:http://www.cplusplus.com/reference/algorithm/search/

wpDiscuz