Recursion

Given the root node of a binary tree `root`

, return the height of the tree.

**Example:**

**Explanation:** This tree is 4 nodes tall.

First Few Test Cases:

1. Recursion

To solve this problem recursively, we have to write the height of the tree `height(root)`

using the heights of other nodes.

You might get stuck here, but remember - whenever you look for a recursion, you should *always* think about nodes that are near the original `root`

node. This means 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.

Mark as Completed: