Determining if a binary tree is balanced (Tricky!!)

This question is asked at several top tech companies and sounds deceptively simple.

Here’s the problem:

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

The above tree is balanced. The left tree has a height of one and the right tree has a height of two.

We’ll go over two solutions: one is a bit easier to understand but with a slower runtime, and the second takes a bit of cleverness but has a faster runtime.

1. Finding the height for every node and ensuring balance

A straightforward way to think about this problem is to calculate the height of the left and right subtrees, and return if they differ by more than 1. So let’s write a function, “height”, which is pretty clear.

Then, we’ll write another helper function that we call on root simply compares the height of the left and right subtrees, and then also checks that the left and right subtrees are *also* balanced. Why do we also need to check that the left and right subtrees are balanced? Well, the height function only returns the *maximum* height of the left and right subtrees, but the subtrees themselves could be imbalanced.

Note that the runtime here is O(N²). We’re doing a lot of repeated calculations because we’re going from the top of the tree to the bottom, and recalculating the height every time.

How can we optimize this? What if we go from the bottom of the tree and work upwards, and for each layer we go up, we can just add 1 to the height?

“Wait, isn’t that we do for the first solution?” you ask. Yes, but now let’s also return as soon as we know we have an imbalanced tree! The first solution would check the current node’s left and right nodes, then check the balance of the left and right nodes, and their left and right nodes, and so on. The new solution we’ll come up with doesn’t need to do those calculations again, so this is just an O(N) solution!

2. Optimized solution

Now that we have a bit of intuition on how to write up this solution, brace yourself, because we’ll do something a bit hacky — we want one function that tells us the height of a node, but also tells if at the current node it’s already an imbalanced tree.

Said another way, the function will do two things:

1/ If at the node we already know the tree is imbalanced, we’ll return -1. You can think of -1 as a “flag” variable that tells us that the tree is imbalanced (a height can never be negative!)

2/ If not, we’ll just return the height of the node.

Let’s walk through a case, which is not a balanced binary tree.

We’ll see that the helper function navigates all the to the bottom left node. Then, when it checks node.left again, it will be null, and return 0. It then goes back to the previous frame, and checks node.right, which is also null, and returns 0. So now abs(l-r) == 0, and we return max(0,0) + 1. So at the bottom left node, we have a height of 1.

Then going to the 3 node right above, we see that l and r will have values of 1 (r has a height of 1 for the same reasoning as the left-most 4 node), and it’s still balanced, so we pass a height of 2 up to the call of helper(node) where node has a value of 2 to the left of the 1 node.

Then all the way back top at the 1 node, we see the left node has a height of 3 and the right node has a height of 1 and thus we return -1, and we exist the helper, and return False.

I know this is a bit confusing so let me know if you have more questions!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!