## Similar Problems

Similar Problems not available

# Subtree Of Another Tree - Leetcode Solution

## Companies:

LeetCode: Subtree Of Another Tree Leetcode Solution

Difficulty: Easy

Topics: tree binary-tree depth-first-search

The Subtree Of Another Tree problem on LeetCode asks you to determine if a given binary tree is a subtree of another binary tree.

Here is the problem statement:

Given two non-empty binary trees `s`

and `t`

, check whether tree `t`

has exactly the same structure and node values with a subtree of `s`

. A subtree of `s`

is a tree consists of a node in `s`

and all of this node's descendants. The tree `s`

could also be considered as a subtree of itself.

Example 1:

Given the following tree s:

```
3
/ \
4 5
/ \
1 2
```

Given the following tree t:

```
4
/ \
1 2
```

Return true, because t has the same structure and node values with a subtree of s.

Example 2:

Given the following tree s:

```
3
/ \
4 5
/ \
1 2
/
0
```

Given the following tree t:

```
4
/ \
1 2
```

Return false.

The solution to this problem can be approached using recursion. To check if tree `t`

is a subtree of `s`

, we need to check if tree `t`

is a subtree of both the left and right subtrees of `s`

.

We can define a helper function called `isSameTree`

that checks if two trees are the same. This function can be called recursively to check if the subtree of `s`

at each node is the same as `t`

.

Here is the solution in Python:

```
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not s:
return False
if self.isSameTree(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:
if not s and not t:
return True
if not s or not t:
return False
if s.val != t.val:
return False
return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
```

In the `isSubtree`

function, we first check if `s`

is empty. If `s`

is empty, then `t`

cannot be a subtree of `s`

.

Next, we check if the root nodes of `s`

and `t`

are the same using the `isSameTree`

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

is a subtree of `s`

.

If the root nodes of `s`

and `t`

are not the same, then `t`

may be a subtree of the left subtree or the right subtree of `s`

. We recursively call the `isSubtree`

function on the left and right subtrees of `s`

.

In the `isSameTree`

function, we first check if `s`

and `t`

are both empty. If they are both empty, then they are the same.

If one of `s`

or `t`

is empty but the other is not, then they are not the same. If the values of the root nodes of `s`

and `t`

are different, then they are not the same.

If the values of the root nodes of `s`

and `t`

are the same, then we recursively check if their left and right subtrees are the same.

This solution has a time complexity of O(m*n) in the worst case, where m and n are the number of nodes in `s`

and `t`

, respectively. This is because we need to check if `t`

is a subtree of each node in `s`

. However, in practice, the time complexity is much lower because we can usually prune the search early.

## Subtree Of Another Tree Solution Code

`1`