LeetCode 110 · Trees

Balanced Binary Tree, explained with a picture

Is the hanging mobile balanced?.

EasyTrees
▶ Watch it step by step

The problem

A binary tree is height-balanced if, at every node, the heights of its left and right subtrees differ by at most 1. Decide whether a tree is balanced.

Input:  [3, 9, 20, null, null, 15, 7]
Output: true

Picture it

Picture a hanging mobile. It is balanced if at every hook the two sides hang to nearly the same depth (difference 0 or 1). We measure from the bottom up: each hook reports its height, or shouts “tipped!” (−1) if anything below it was unbalanced, and that shout passes straight up to the top.

How to recognise it

  • The input is a binary tree and the question is a yes/no check that every node must pass.
  • The check at a node needs the heights of its two subtrees, which are built from the children's heights. That points to a bottom-up depth-first search (DFS: follow one branch to the bottom before trying the next).
  • One failure anywhere decides the answer, so a failure should travel up quickly.
  • Up to 5,000 nodes. A slower approach passes, but one visit per node is the clean solution.

Start with brute force

Follow the definition from the top: at each node, compute both subtree heights from scratch, compare them, then check both children the same way.

def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

def is_balanced_brute(root):
    if not root:
        return True
    if abs(height(root.left) - height(root.right)) > 1:
        return False
    return is_balanced_brute(root.left) and is_balanced_brute(root.right)

Each node's height is recomputed once for every ancestor that gets checked, so time is O(n · h), where h is the height: about n log n for a balanced tree. With 5,000 nodes this still passes LeetCode, but on bigger trees the repeated walks add up, and the next idea removes them for free.

From brute force to the idea

  1. Find the waste. height(root.left) already computes the height of every node in the left subtree, then throws those numbers away. The checks below repeat them.
  2. Check while measuring. Compute heights bottom-up once. At each node, as soon as l and r are known, test abs(l - r) > 1.
  3. Send failure up with a sentinel. Heights are never negative, so return -1 to mean "unbalanced somewhere below". A parent that receives -1 from either child returns -1 too, without needing its own check.
  4. Read the answer at the root. The tree is balanced exactly when the root's result is not negative: height(root) >= 0.

This is the key idea: one post-order DFS (children before the node) returns heights, and a -1 sentinel carries any imbalance to the top.

The shown code still recurses into the right child after the left one has returned -1; it only skips the comparison. You can add if l < 0: return -1 before the right call to stop earlier. The worst case stays O(n).

The key idea

Compute heights bottom-up and return −1 as soon as a node is unbalanced. One pass, O(n).

Python solution

def is_balanced(root):
    def height(node):
        if not node:
            return 0
        l = height(node.left)
        r = height(node.right)
        if l < 0 or r < 0 or abs(l - r) > 1:
            return -1                  # unbalanced below
        return 1 + max(l, r)
    return height(root) >= 0

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n · h): heights recomputed for each checked ancestor, about n log n when balancedO(h): recursion only
Height with sentinel (shown code)O(n): each node visited once, O(1) workO(h): one stack frame per level, h = n for a chain

Edge cases

  • Empty tree: height(None) is 0, so it returns True.
  • Single node, or a root with one leaf child ([1, 2]): True; heights 1 and 0 differ by 1.
  • Chain of three ([1, 2, null, 3]): False; the root's subtrees have heights 2 and 0.
  • Balanced root, unbalanced child ([1, 2, 2, 3, null, null, 3, 4, null, null, 4]): False; both root subtrees have height 3, but each 2 has heights 2 and 0 below it.
  • Very deep tree: about 1,000 levels hits Python's default recursion limit, but a tree that deep with at most 5,000 nodes is badly unbalanced anyway. The recursion still descends to the bottom before returning, so RecursionError is possible.

Common mistakes

  • Checking only the root's two subtree heights, which misses an imbalance lower down.
  • Comparing node counts instead of heights. Heights 2 and 1 are fine even when the subtrees have 3 nodes and 1 node.
  • Forgetting the l < 0 or r < 0 test, so -1 is treated as a real height and an imbalance below can be hidden.
Your turn: balanced by size

Call a tree size-balanced if, at every node, the number of nodes in the left and right subtrees differs by at most 1. [1, 2, 3, 4] is size-balanced; [1, 2, 3, 4, 5] is not (3 nodes against 1) although it is height-balanced. Decide whether a tree is size-balanced. Describe your approach, then write it if you like.

Compare with our answer

Same pattern: return a measurement bottom-up, with -1 as the failure sentinel. Only the measurement changes, from height to size.

def is_size_balanced(root):
    def size(node):
        if not node:
            return 0
        l, r = size(node.left), size(node.right)
        if l < 0 or r < 0 or abs(l - r) > 1:
            return -1
        return 1 + l + r
    return size(root) >= 0

Time O(n), space O(h).

A strong answer mentions: returning 1 + l + r instead of 1 + max(l, r), keeping the sentinel check, and an example that passes one test but not the other.

Check what stuck

1. You must check that, at every node of a tree, the left subtree's sum is within 10 of the right subtree's sum. Which approach fits best?

2. Why is the shown solution O(n) while the brute force is not?

3. A learner checks only abs(height(root.left) - height(root.right)) <= 1. Which tree is now judged wrongly?

Score 60% or more and the lesson is marked complete.