# 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,

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 –

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

(2 votes, average: 5.00 out of 5)

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 🙂

Subscribe
Notify of
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).

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

Guest
Tommy Bahama

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