1. Recursion

To solve this problem recursively, we have to write the height of the tree height(root) using the heights of other nodes.

Whenever you look for a recursion, you should always think locally near the original problem you're breaking down. Here, this means you should look near the root node. We should try to find a recursion that involves the root.left and root.right:

From this image, you can see that the height of the tree is equal to the height of the tallest child (the blue tree), plus 1. So this is our recursive equation. The same way that 1 + 1 = 2, here's what the recursion is equal to:

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. Since we can't use the recursion to get what height is equal to in this case, we need to manually find what it's equal to. The height of no node is just equal to 0.

3. Code

To code the solution, you should write a function that always returns whatever height is equal to. That way it's guaranteed to be correct. It's equal to the recursion, unless we're in the base case in which case it's equal to 0. Here's the full code:

Time Complexity $O(n)$. We visit all $n$ nodes, which takes $O(n)$ time.

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