1. Recursion

To solve this problem, we want to find a recursion for whether the trees are equal. We need to write treesEqual(p, q) using treesEqual(other node, other node).

Two trees are equal if the values of the roots are equal, and if the left subtrees are equal, and if the right subtrees are equal.

So we can literally just take this idea and convert it to a recursive equation. Here's the recursion:

2. Base case

The recursion calls itself on lower and lower nodes in the tree, until it eventually gets to a node that's null. This is where the recursion breaks (we'll get an error). Since we can't use the recursion to get what treesEqual is equal to in this case, we need to manually find what it's equal to.

There are 3 cases where the node is null. Either p is null, or q is null, or both nodes are null:

3. Code

To get the solution, we just create a function that always returns what treesEqual is equal to. That way it's guaranteed to be correct. It's always equal to the recursion, unless we're in the base case, in which case it's equal to that instead. Here's the full code:

Time Complexity $O(\min(m, n))$, where $m$ is the number of nodes in the first tree and $n$ is the number of nodes in the second tree. We compare nodes until we find a mismatch, and then we stop comparing. This means in the worst case, we visit every node in the smaller tree.

Space Complexity $O(\min(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.