Balanced Binary Tree: Bottom-Up Height Check

You are given the root of a binary tree. Determine if it is height-balanced. A binary tree is height-balanced if, for every node, the heights of the left and right subtrees differ by no more than 1.

This is LeetCode 110: Balanced Binary Tree, and it is one of the cleanest examples of bottom-up tree validation. Instead of checking the balance condition top-down (which would recompute heights over and over), you compute height from the leaves up and detect any imbalance along the way. One pass, one traversal, done.

Why this problem matters

If you have solved Maximum Depth of Binary Tree, you already know how to compute height recursively. That same 1 + max(left, right) pattern is the backbone of this problem. The new idea is layering a validation check on top: at every node, before you return the height, you verify that the left and right subtrees do not differ by more than 1.

The elegant twist is how you signal failure. Instead of carrying a separate boolean through the recursion, you use -1 as a sentinel value. If any subtree is unbalanced, the function returns -1, and that -1 propagates all the way up. The moment you see -1, you stop doing real work and just pass -1 along. This gives you early termination for free.

The approach

The strategy is bottom-up DFS:

1. Recurse to the leaves. A null node has height 0.
2. At each node, get the height of the left subtree and the height of the right subtree.
3. If either child returned -1, this subtree is already unbalanced. Return -1.
4. If the absolute difference between left and right heights is greater than 1, this node is the point of imbalance. Return -1.
5. Otherwise, return 1 + max(left, right) as the height.

At the top level, check whether the final return value is -1.

The solution

def is_balanced(root):
    def height(node):
        if node is None:
            return 0
        left = height(node.left)
        if left == -1:
            return -1
        right = height(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return height(root) != -1

Let's walk through each piece:

• if node is None: return 0 is the base case. A null node has height 0. This is the recursive null base case pattern that appears in every tree height computation.
• left = height(node.left) gets the height of the left subtree. If it returns -1, the left subtree is already unbalanced, so we immediately return -1 without even checking the right side.
• right = height(node.right) does the same for the right subtree, with the same early exit on -1.
• if abs(left - right) > 1: return -1 checks the balance condition at this node. If the two subtrees differ by more than 1 in height, this node violates the balanced property.
• return 1 + max(left, right) returns the normal height when everything is balanced.

Visual walkthrough

Let's trace the recursion through the tree [3, 9, 20, null, null, 15, 7] step by step. At every node, watch the height values flow up and the balance check pass at each level.

The key observation is that every node checks abs(left - right) before returning its height. At node 9, the difference is |0 - 0| = 0. At node 20, it is |1 - 1| = 0. At the root, it is |1 - 2| = 1. None of these exceed 1, so no node returns -1, and the final result is height(root) != -1, which is True.

If any single node had found a difference greater than 1, it would have returned -1. That -1 would have propagated up through every ancestor, and the final check would have returned False.

Complexity analysis

Time is O(n). Every node is visited at most once. At each node you do O(1) work: two comparisons and one addition. The early termination means you might visit fewer than n nodes if the tree is unbalanced deep in a subtree, but the worst case is still O(n).

Space is O(h) where h is the height of the tree. That is the depth of the recursion stack. For a balanced tree, h = log n. For a completely skewed tree, h = n.

Edge cases to watch for

• Empty tree (root is None): return True. The base case returns 0, which is not -1, so the tree is balanced. An empty tree is trivially balanced.
• Single node: return True. Both children are null, so left = 0, right = 0, difference is 0. Height is 1.
• Left-heavy tree (long left chain, no right children): if the left subtree is more than 1 level deeper than the right at any node, the function returns -1 at that node.
• Perfectly balanced tree: every node has equal left and right heights. The function never returns -1 and computes the full height.

The building blocks

This problem is built on two fundamental building blocks:

1. Bottom-up tree validation (bottom-up-tree-validation). Instead of checking a property top-down and recomputing values at every node, you compute values bottom-up and validate as you go. The skeleton looks like this:

def validate(node):
    if node is None:
        return BASE_VALUE
    left = validate(node.left)
    if left == INVALID:
        return INVALID
    right = validate(node.right)
    if right == INVALID:
        return INVALID
    if VIOLATION(left, right):
        return INVALID
    return COMBINE(left, right)

For Balanced Binary Tree, BASE_VALUE is 0, INVALID is -1, VIOLATION checks abs(left - right) > 1, and COMBINE is 1 + max(left, right). This same bottom-up validation pattern applies to any tree problem where you need to verify a property that depends on subtree information.

2. Early termination with sentinel (early-termination-sentinel). Using -1 as a sentinel means you do not need a separate boolean variable or a global flag. The -1 value encodes "already failed" directly in the return value. When a parent sees -1 from a child, it immediately returns -1 without doing further work. This pattern keeps the code compact and avoids unnecessary computation.

The combination of these two building blocks is what makes this solution clean. You already know how to compute height recursively from Maximum Depth of Binary Tree. The new layer is the validation check with early termination: at each node, verify the balance condition, and if it fails, signal failure with -1 so that every ancestor can bail out immediately.

From understanding to recall

You just read through a solution that computes height bottom-up and uses -1 as a sentinel for imbalance. You traced through the recursion and saw how every node checks abs(left - right) > 1 before returning. It all clicks right now.

But in an interview, will you remember to check for -1 before recursing into the right subtree? Will you remember that the function returns -1 on failure instead of False? Or will you default to the naive O(n^2) approach because the bottom-up trick slipped your mind?

Understanding is not recall. You understood the solution. Recall means you can write it cold, under pressure, without confusing the sentinel approach with a global-flag approach or forgetting the early exit checks.

Spaced repetition builds recall. You practice typing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the base case, the -1 checks, the balance validation, and the height return from memory. After a few repetitions, the bottom-up-tree-validation pattern and the early-termination-sentinel pattern are automatic.

These two building blocks are part of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - Uses the same height recursion without the balance check. Solve this first if you have not already.
• Diameter of Binary Tree - Another bottom-up tree problem where you compute one value (depth) and track a different property (diameter) during the same traversal.