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.