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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
// Function to store in-order traversal of the tree in a vector void inorder(Node* node, vector<Node *> &vc) { if (node == nullptr) return; inorder(node->left, vc); vc.push_back(node); inorder(node->right, vc); } // Function to store post-order traversal of the tree in a vector void postorder(Node* node, vector<Node *> &vc) { if (node == nullptr) return; postorder(node->left, vc); postorder(node->right, vc); vc.push_back(node); } // Function to check if given binary tree is a subtree of another // binary tree or not bool checkSubtree(Node *tree, Node *subtree) { // base case: both trees are same if (tree == subtree) return true; // base case: if first tree is empty but second tree is non-empty if (tree == nullptr) return false; // store in-order traversal of both trees in v1 and v2 respectively vector<Node *> v1, v2; inorder(tree, v1); inorder(subtree, v2); // return false if v2 is not a sub-array of v1 if (search(v1.begin(), v1.end(), v2.begin(), v2.end()) == v1.end()) return false; // reset both vectors v1.erase(v1.begin(), v1.end()); v2.erase(v2.begin(), v2.end()); // Now store post-order traversal of both trees in v1 and v2 resp postorder(tree, v1); postorder(subtree, v2); // return false if v2 is not a sub-array of v1 if (search(v1.begin(), v1.end(), v2.begin(), v2.end()) == v1.end()) return false; return true; } // main function int main() { Node* root = nullptr; /* Construct below tree 1 / \ / \ 2 3 / \ / \ 4 5 6 7 */ checkSubtree(root, root->right)? cout << "Yes": cout << "No"; return 0; } |

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n).

**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

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/

Thanks Avishek. We have updated the complexity.

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

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