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
- 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. - Check while measuring. Compute heights bottom-up once. At each node, as soon as
landrare known, testabs(l - r) > 1. - Send failure up with a sentinel. Heights are never negative, so return
-1to mean "unbalanced somewhere below". A parent that receives-1from either child returns-1too, without needing its own check. - 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) >= 0In 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · h): heights recomputed for each checked ancestor, about n log n when balanced | O(h): recursion only |
| Height with sentinel (shown code) | O(n): each node visited once, O(1) work | O(h): one stack frame per level, h = n for a chain |
Edge cases
- Empty tree:
height(None)is 0, so it returnsTrue. - 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
RecursionErroris 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 < 0test, so-1is treated as a real height and an imbalance below can be hidden.
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.
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?
The structure is the same as balanced height: measure bottom-up and check as you go, in O(n). Separate sum calls repeat work, and root-only or per-level checks miss nodes deeper down. Any negative sum is possible here, so use None as the sentinel instead of -1.
2. Why is the shown solution O(n) while the brute force is not?
Bottom-up, a parent gets its children's heights as return values, so nothing is recomputed. No dictionary is needed, and every node is visited when the tree is balanced.
3. A learner checks only abs(height(root.left) - height(root.right)) <= 1. Which tree is now judged wrongly?
In the last tree both root subtrees have height 3, so the root-only test says balanced, but each node 2 has heights 2 and 0 below it. In the other trees the root itself shows the right answer.
Score 60% or more and the lesson is marked complete.