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

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