Recursion

Given two roots of binary trees `root`

and `subRoot`

, return whether the $\small \tt root$ tree contains the $\small \tt subRoot$ tree as a subtree.

A "subtree" is defined as a node in the original tree, and all of its descendants.

**Example 1:**

$\notag \large \texttt{=> returns True}$

**Example 2:**

$\notag \large \texttt{=> returns False}$

**Explanation:** The subtree `[2,9,4,None,3]`

is not equal to the $\small \tt subRoot$ tree `[2,9,4]`

.

First Few Test Cases:

1. Recursion

To solve this problem, we want to find a recursion for containsSubtree(root, subRoot).

We want to check if the root is equal to the subtree `treesEqual(root, subRoot)`

, or if the subtree is contained in the left or right trees. Here's the recursion for this:

Note that the treesEqual function shows up, but we already make this function in a different problem, so we'll just copy that code.

2. Base case

The recursion calls itself on lower and lower nodes in the tree. Eventually, it gets to a node that's null `containsSubtree(null, subRoot)`

. This gives an error, and we need to manually find what it's equal to. A null tree does not have any subtrees, so it's just False.

3. Code

To code this up, you should write a function that returns what `isSubtree`

is equal to. This way it's guaranteed to be correct. `isSubtree`

is always equal to the recursion, unless we're in the base case in which case it's False. Here's the full code:

Time Complexity $O(m \cdot n)$ worst case. We go through all $n$ nodes in the `root`

tree, and at each node we check if that node's tree is equal to the `subRoot`

tree, potentially checking $O(m)$ nodes. Multiplying these gives $m\cdot n$.

Space Complexity $O(m+n)$. For now, you don't need to know where this comes from - we'll go over the full details in the next lesson "Call Stack". Just know the computer needs some memory to keep track of the function calls it's making.

Mark as Completed: