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

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

newest oldest most voted
Notify of
Avishek Dutta
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).



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