LeetCode 110 – Balanced Binary Tree

Balanced Binary Tree has a correct answer that most people write and a better one that takes the same number of lines. The gap between them is a single idea — make the return value carry two pieces of information — and that idea is behind a whole family of tree problems, so it is worth spending the extra minute on.

The problem

Return whether a binary tree is height-balanced: at every node, the heights of the two subtrees differ by at most 1.

      3
     / \        -> true
    9   20
       /  \
      15   7

        1
       / \
      2   2     -> false
     / \
    3   3       the root's subtrees have heights 3 and 1
   / \
  4   4

  []            -> true

"At every node" is the part to read twice. A tree whose root looks balanced can still fail deeper down, so this is not a property you check once.

The obvious solution, and what it costs

Write a height function, then at each node compare the two heights and recurse:

isBalanced(node):
    |height(node.left) - height(node.right)| <= 1
    and isBalanced(node.left)
    and isBalanced(node.right)

Correct, and it recomputes heights relentlessly. The root's height call walks the whole tree; then each child does it again for its own subtree, and so on. On a balanced tree that is O(n log n); on a degenerate one it is O(n²).

This is the same overlapping-work smell as the naive recursion in Climbing Stairs, and the fix has the same character: compute each height once and use it on the way back up.

One pass, with a sentinel

The obstacle is that a single recursion seems to need two return values — the height, and whether the subtree is balanced. In a language without tuples the usual answer is a wrapper class, which works and is verbose.

The neater move: heights are non-negative, so -1 is free to mean "not balanced". One integer carries both answers.

height(null) = 0
height(node):
    left  = height(node.left);   if left  == -1 return -1     propagate failure
    right = height(node.right);  if right == -1 return -1
    if |left - right| > 1        return -1                    fail here
    return 1 + max(left, right)

Failure propagates upward without unwinding the whole computation, and the first imbalance found short-circuits everything above it. The tree is balanced exactly when the root returns something other than -1.

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    /** Height of this subtree, or -1 if it (or anything below it) is unbalanced.
     *  Heights are never negative, so -1 is a free sentinel. */
    private int height(TreeNode node) {
        if (node == null) return 0;

        int left = height(node.left);
        if (left == -1) return -1;              // already failed below -- stop early

        int right = height(node.right);
        if (right == -1) return -1;

        if (Math.abs(left - right) > 1) return -1;

        return 1 + Math.max(left, right);
    }
}

Checking left == -1 before computing right is deliberate: once the left subtree has failed there is no reason to walk the right one at all. Computing both and then testing is still correct but throws away the early exit.

The public method is one line, and all the work is in the helper whose contract is written in the comment. If you use a sentinel, document what it means — an unexplained -1 is exactly the kind of cleverness that reads as a bug during code review.

Python

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(node: TreeNode) -> int:
            """Height of this subtree, or -1 if anything in it is unbalanced."""
            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

Python has tuples, so return (is_balanced, height) is available and arguably clearer. Mention it — the sentinel is a Java-shaped solution, and choosing it in Python is a choice rather than a necessity. Either answer is fine; not knowing there was a choice is not.

Complexity

Each node's height is computed exactly once, so the one-pass version is linear. The early exit makes unbalanced trees faster still, though the worst case — a balanced tree, where nothing exits early — is unchanged.

The pattern

"Return one quantity up while checking or recording another" is the reusable idea. Diameter of Binary Tree (543) returns the depth and records the diameter in a field. Binary Tree Maximum Path Sum (124) returns the best downward path and records the best through-path. This problem folds the second channel into the return value itself using a sentinel.

Three ways to carry two answers out of one recursion — a sentinel, an outer variable, or a tuple — and knowing all three means never being stuck when a tree problem needs more than one number per subtree.

What the interviewer is checking

• That balance is required at every node, not just the root.
• That you notice the naive version recomputes heights, and can state its complexity.
• The sentinel, and that you document what -1 means.
• That failure propagates upward and short-circuits.
• Empty tree and single node.
• A tree that is balanced at the root and unbalanced deeper down.
• That you know the tuple and outer-variable alternatives exist.