# 572. Subtree of Another Tree — LeetCode(Python)

I got you!

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

# Solution:

## identical() helper function —

Consider reading my solution for ** 100. Same Tree — LeetCode(Python)** to better understand the code above.

We need a helper function to judge if the two subtrees we are considering are in-fact identical.

## 1. Iterative Approach (BFS) —

## Explanation —

We can use a breadth-first search (BFS) traversal algorithm to iteratively solve the problem.

A queue is used to store all nodes in the tree level by level.

At every step, we pop / dequeue an element from the queue. If this node has a value equal to that of the ** subTree**’s root, we check if both the subtrees are identical or not.

*True*is returned if they are.

The, we append the left and right children of the current node into our stack.

The *while* loop terminates when the ** queue** is empty, which means all nodes in the tree have been traversed and popped out from the

*queue.*So, now it is safe to say that no such subtree was found in our given tree. Therefore, we return *False.*

## Time and Space Complexity —

We are visiting each node in the tree only a constant number of times in our BFS code, but we are calling identical() at every valid node, so we can say that our algorithm requires quadratic amount of time to run in the worst case.

Also, our queue will be storing a maximum of (n / 2) nodes when it reaches the final level. So, we assume the space complexity to be linear in the worst case, per tree — therefore, quadratic.

Thus, if *m* and *n* are the number of nodes in the given binary trees,

Time Complexity: O(mn)

Space Complexity: O(mn)

## 2. Recursive Approach (DFS) —

## Explanation —

We could also use a depth-first search (DFS) traversal algorithm to solve this problem recursively.

We simply return True if the ** subTree** is empty, because then our tree will have a copy of it. [this clause can be omitted because we are given that the

**will have a positive number of nodes]**

*subTree*The base case of our recursion would be when we reach a leaf node in our tree, which is when we return *False.*

Else, we check if the current node in the tree is where our ** subTree** is rooted at. If yes, we return

*True.*

Otherwise we return the value of the recursive search on the *left* and *right *children of the current node.

## Time and Space Complexity —

We are visiting each node in the tree only a constant number of times in our BFS code, but we are calling identical() at every valid node, so we can say that our algorithm requires quadratic amount of time to run in the worst case.

Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case, per tree — therefore, quadratic.

Thus, if *m* and *n* are the number of nodes in the given binary trees,

Time Complexity: O(mn)

Space Complexity: O(mn)