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 of Binary Tree
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).

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Avishek Dutta
Guest

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/

Guru
Guest

Even if we use extra space and store inorder/preorder in separate arrays, finding out if one array is a subset of another will be o(mxn) problem

Tommy Bahama
Guest

Yes, but here every element appears only once, which allows you to just match the the starting node of the subset candidate and just check if the following elements match as well giving you O(N+M).