# LeetCode: 572. Subtree of Another Tree

**The Problem**

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

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

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
return isSameTree(root, subRoot) ||
(root != nullptr &&
(
isSubtree(root->left, subRoot) ||
isSubtree(root->right, subRoot)
)
);
}
bool isSameTree( TreeNode *root, TreeNode *sub ) {
if ( root == nullptr ) return sub == nullptr;
else if ( sub == nullptr ) return false;
return root->val == sub->val &&
isSameTree( root->left, sub->left ) &&
isSameTree( root->right, sub->right );
}
```

ðŸ§

Github with all the solution including test cases.

Let's break down the code step by step:

**Function Definitions:**

`isSubtree(TreeNode* root, TreeNode* subRoot)`

: This function checks if a binary tree named`subRoot`

is a subtree of another binary tree named`root`

.`isSameTree(TreeNode* root, TreeNode* sub)`

: This function checks if two binary trees, one named`root`

and the other`sub`

, are exactly the same.

**isSameTree Function:**

- This function is used to compare two binary trees, checking if they are exactly the same in structure and node values.
- It takes in two parameters,
`root`

and`sub`

, which are the roots of the two binary trees being compared. - If
`root`

is`nullptr`

(i.e., the tree is empty), the function returns`true`

if`sub`

is also`nullptr`

, indicating both trees are empty. If`sub`

is not`nullptr`

, it means the trees are not the same. - If
`sub`

is`nullptr`

, it means we are comparing a non-empty tree (`root`

) with an empty tree (`sub`

), so the function returns`false`

. - Finally, the function compares the node values of the current nodes in both trees (
`root->val`

and`sub->val`

). If the values are the same, it recursively calls itself on the left and right subtrees of both trees (`root->left`

,`sub->left`

,`root->right`

, and`sub->right`

), effectively checking each corresponding pair of nodes in both trees.

**isSubtree Function:**

- This function is used to check if one binary tree (named
`subRoot`

) is a subtree of another binary tree (named`root`

). - It first checks if
`subRoot`

is exactly the same as`root`

using the`isSameTree`

function. If they are the same, then`subRoot`

is indeed a subtree of`root`

. - If
`subRoot`

is not the same as`root`

, the function proceeds to check if`subRoot`

is a subtree of the left subtree of`root`

or the right subtree of`root`

. - It does this by recursively calling itself on both the left and right subtrees of
`root`

and checking if either of them contains`subRoot`

.