Balanced Binary Tree

Balanced Binary Tree looks like it needs two passes — one to measure heights, one to check balance — but the classic trick folds both into a single bottom-up DFS. It is the canonical lesson in returning extra information up the recursion.

The slow way first

The obvious approach: write a height(node) helper, then at every node call height(left) and height(right) and compare them. The problem is that height walks the entire subtree, and you call it at every node — so the same nodes get visited again and again. That is O(n²) on a skewed tree.

The question to ask: while I am computing a height, can I check balance at the same time? Yes — the balance check only needs the two child heights, which the recursion already produces.

The idea: return height, or -1 for unbalanced

Do one bottom-up DFS that returns a node's height. But overload the return value: if a subtree is unbalanced, return -1 as a sentinel instead. At each node, if either child returned -1, or the two child heights differ by more than 1, this node is unbalanced — return -1. Otherwise return the real height 1 + max(left, right). The -1 poisons every ancestor, so it shoots straight to the top.

The insight: a single value carries two meanings — a non-negative number is the height, and -1 means unbalanced. That lets one pass do the work of two.

Walk through it

Step through the animation. DFS dives to the leaves first; each leaf returns height 1. Climbing back up, node 20 sees child heights 1 and 1 (|1 − 1| = 0), so it returns 2. The root 3 sees 1 and 2 (|1 − 2| = 1), still within the limit, so it returns 3. No call ever returned -1, so the answer is true.

Pseudocode

define dfs(node):
    if node is empty:
        return 0                          # empty subtree has height 0
    left  = dfs(node.left)
    right = dfs(node.right)
    if left is -1 or right is -1:
        return -1                         # a child was already unbalanced
    if abs(left - right) > 1:
        return -1                         # this node is unbalanced
    return 1 + max(left, right)           # height of this subtree
answer = dfs(root) is not -1

The Python solution

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

• dfs returns the height of a subtree, or -1 if anything below it is unbalanced.
• The None base case returns 0 — an empty subtree contributes no height.
• We recurse into both children first, so heights bubble up from the bottom.
• Line 7 is the heart: if either child is poisoned (-1) or the heights differ by more than 1, this node fails and returns -1, which propagates upward and stops further work.
• Otherwise the height is 1 + max(left, right). At the top, dfs(root) != -1 turns the sentinel into a clean boolean.

Complexity

We visit each node exactly once, so time is O(n). The extra space is the recursion stack, O(h) where h is the tree height — O(log n) for a balanced tree, O(n) in the worst (skewed) case.

When this pattern shows up

Practice