Tree Contains Subtree

Given two roots of binary trees root and subRoot, return whether the root\small \tt root tree contains the subRoot\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:

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

Example 2:

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

Explanation: The subtree [2,9,4,None,3] is not equal to the subRoot\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(mn)O(m \cdot n) worst case. We go through all nn 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)O(m) nodes. Multiplying these gives mnm\cdot n.

Space Complexity O(m+n)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:
Test your code to get an output here!
Test your code to get an output here!