Recursion

Height-Balanced Tree

Given the root node of a tree root, determine whether the tree is height-balanced.

A tree is height balanced if for every node in the tree, the heights of its two children are within one of each other.

Example:

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

Explanation: The height of the left subtree and right subtree are all within one of each other. For example:

This holds for every node in the tree, so the tree is height balanced.

First Few Test Cases:

A tree is height balanced if every node follows the equation below. The equation just says the heights of the two children are within one of each other.

We could try to write a recursion to check this, but that's actually really hard. So now what? The trick is to make height recursive, and "hijack" it. After all, we definitely need to compute height at each node.

1. Recursion

We already know the recursive equation for the height from a previous problem. Here it is:

This equation is recursive, which means it calls itself on literally every node in the tree, and finds its height. This means the recursion is already computing everything we need in order to check if the tree is height balanced. A clever idea is to "hijack" this recursion, and stick in a few lines of code so that it also computes if the tree is height balanced, like this:

2. Base case

The recursion stops when we get to a null node. In that case, the height is 0.

3. Code

To code this up, we combine the recursion and the base case. We use a global variable called "balanced" which we update as we hijack the function. Once we see that the tree is not balanced, we'll set it to False. Here's the code:

Time Complexity O(n)O(n). We visit every node once and do O(1) operations per node, giving O(n)*O(1) = O(n).

Space Complexity O(n)O(n). height calls itself until it reaches a null node, so it might get nn calls deep (the tree might be a flat line). This means the Call Stack might grow up to size nn.

Mark as Completed:
Submits:
heightBalanced
Imports:
TreeNode
Test your code to get an output here!
heightBalanced(
)
Test your code to get an output here!