# Subtree of Another Tree

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

--

--

## More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

## Jaydeep

Full Stack Programmer, love to solve problem’s during free time.