Subtree of Another Tree

Photo by Matthew Smith on Unsplash

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Constraints:

• The number of nodes in the root tree is in the range [1, 2000].
• The number of nodes in the subRoot tree is in the range [1, 1000].
• -104 <= root.val <= 104
• -104 <= subRoot.val <= 104

Algorithm -

1. Find the node in the root tree which matches with the root of subTree.
2. Once found we can check the subtree of root tree is same as subTree.
3. We first compare the root with subTree.
4. If both the trees are not same, go to the left of root and compare the left subtree with the given subTree.
5. If in step 4 we did not find the same tree, we compare right subtree with input subTree.
6. If we did not find match at step 4 and 5, we recursively traverse the left and right subtree of root and check for is same tree.

Runtime: 130 ms.

Memory Usage: 47.6 MB