Problem
Given the root of a binary tree, decide whether it is height-balanced: at every node, the heights of the left and right subtrees differ by at most 1. Return True if the whole tree satisfies this, False otherwise. An empty tree counts as balanced.
The condition must hold at every node, not just the root. A tree can be balanced at the root while an unbalanced subtree hides deeper down.
Examples
Example 1
Input: root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output: True
At every node the left/right heights differ by at most 1.
Example 2
Input: root = [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
Output: False
At the left child 2, the left subtree has height 2 but the right subtree has height 1 below it — and at the root, left height 3 vs right height 1 breaks the rule.
Example 3
Input: root = []
Output: True
An empty tree is balanced by definition.
Constraints
- The number of nodes is in
[0, 5000]. O(n) is expected; O(n^2) passes but is the brute force an interviewer will ask you to beat.
-10^4 <= Node.val <= 10^4. Values do not matter; only the tree’s shape does.
Think about it first
Hint 1
You already know how to compute the height of a tree recursively. Balance at a node is a statement about two heights.
Hint 2
Checking balance at every node by recomputing heights repeats work: the height of a node is recomputed once for each of its ancestors. Can one traversal answer both questions at once?
Hint 3
Do a post-order DFS that returns the subtree height, but return a sentinel like `-1` as soon as any subtree is unbalanced. The failure propagates straight up without further work.
TL;DR
Bottom-up post-order DFS returning height or a -1 “unbalanced” sentinel — O(n) time, O(h) space.
Approach 1 — Brute force: top-down height checks
The direct approach: for each node, compute the height of its left and right subtrees, compare them, then recurse into both children to check that they are balanced too.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional
def isBalanced(root: Optional[TreeNode]) -> bool:
def height(node: Optional[TreeNode]) -> int:
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
if not root:
return True
if abs(height(root.left) - height(root.right)) > 1:
return False
return isBalanced(root.left) and isBalanced(root.right)
Complexity: O(n^2) time in the worst case (a skewed tree recomputes each height once per ancestor; on balanced trees it is O(n log n)), O(h) space. With n = 5000, a skewed tree costs about 12.5M height steps. It passes, but the redundant recomputation is what the follow-up targets.
Approach 2 — Bottom-up DFS with a sentinel (one pass)
The insight: the brute force computes heights and checks balance in two separate recursions over the same nodes. A post-order DFS processes both children before the node itself, so it already holds both child heights when it visits a node. It can check balance and return the height in a single visit. Encode “unbalanced somewhere below” as the impossible height -1 so a failure short-circuits up the call stack.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional
def isBalanced(root: Optional[TreeNode]) -> bool:
def check(node: Optional[TreeNode]) -> int:
"""Return subtree height, or -1 if unbalanced anywhere within."""
if not node:
return 0
left = check(node.left)
if left == -1:
return -1
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(root) != -1
Walkthrough on [1,2,2,3,3,null,null,4,4] (example 2):
flowchart TD
R["1 (root): left h=3, right h=1, |3-1|=2 -> unbalanced"] --> A["2 (h=3)"]
R --> B["2 (h=1)"]
A --> C["3 (h=2)"]
A --> D["3 (h=1)"]
C --> E["4 (h=1)"]
C --> F["4 (h=1)"]
Post-order reaches the 4 leaves first, each returning height 1. Their parent (left 3) gets left=1, right=1 and returns 2. The right 3 is a leaf and returns 1. Node 2 (left child of root) gets left=2, right=1, and since |2-1| <= 1 it returns 3. The failure appears at the root: left=3 (the tall 2) vs right=1 (the childless 2), so |3-1| = 2 > 1, the root returns -1, and the answer is False. Each height is computed exactly once.
Complexity: O(n) time — every node is visited once. O(h) space for the recursion stack (O(n) worst case on a skewed tree).
Approach 3 — Iterative post-order (no recursion)
The insight: the same bottom-up computation works with an explicit stack if you defer a node until both children’s heights are known; a hash map stores the heights of finished subtrees. Useful for “do it without recursion” follow-ups, or for very deep trees that would exceed Python’s recursion limit.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional, Dict
def isBalanced(root: Optional[TreeNode]) -> bool:
heights: Dict[Optional[TreeNode], int] = {None: 0}
stack = [(root, False)] if root else []
while stack:
node, visited = stack.pop()
if visited:
left = heights[node.left]
right = heights[node.right]
if abs(left - right) > 1:
return False
heights[node] = 1 + max(left, right)
else:
stack.append((node, True))
if node.left:
stack.append((node.left, False))
if node.right:
stack.append((node.right, False))
return True
Walkthrough on [3,9,20,null,null,15,7] (example 1): the stack drills down to leaves 9, 15, 7, recording height 1 for each. Node 20 re-emerges with both children done and gets 1 + max(1,1) = 2. Finally 3 sees left=1, right=2, a difference of 1, so it never returns False and the answer is True.
Complexity: O(n) time, O(n) space (stack plus the heights map).
Common pitfalls
- Checking balance only at the root —
[1,2,2,3,null,null,3,4,null,null,4] is unbalanced even though the root’s two subtrees have equal height.
- Forgetting the empty-tree case:
root = None must return True.
- In the sentinel version, computing
1 + max(left, right) before testing for -1 — the sentinel must propagate unchanged, or -1 becomes a legal-looking height.
- Confusing this with a complete or perfect tree check; height-balanced only bounds the per-node height gap by 1.
Pattern takeaway
When a tree question asks a global yes/no that depends on a per-subtree metric (height, size, sum), compute the metric bottom-up with a post-order DFS and fold the check into the same return value. A sentinel like -1 turns “compute + validate” into one O(n) pass. Recomputing subtree metrics top-down is the classic O(n^2) trap.