Balanced Binary Tree — Solution

Problem

Given a binary tree, determine whether it is height-balanced — meaning for every node in the tree, the height of its left subtree and right subtree differ by at most one.

Balanced example:

[3,9,20,null,null,15,7]

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: true
• Explanation: Node 3 has left height 1 and right height 2, a difference of 1 — still balanced.

Unbalanced example:

[1,2,null,3]

• Input: root = [1, 2, null, 3]
• Output: false
• Explanation: Node 1 has a left subtree of height 2 and an empty right subtree (height 0), a difference of 2.

Intuition

The key observation is that balance depends on height, and height is a bottom-up property — you compute it by returning values from the leaves upward. The trick is to detect imbalance and stop early rather than finishing the traversal when the answer is already known to be false.

Approach 1 — Top-Down Height Checks

For each node, separately compute the height of its left and right subtrees and verify the difference is at most 1, then recurse on both children. This is straightforward but wasteful: the height() call at the root computes heights for the entire tree, and then the recursive calls do it again for every subtree, leading to redundant work.

1. If the node is null, return true (an empty tree is balanced).
2. Compute the height of the left subtree using a helper function.
3. Compute the height of the right subtree.
4. If the absolute difference exceeds 1, return false.
5. Recurse on both children; only balanced if both are balanced.
6. The height() helper returns 0 for null, 1 + max of children otherwise.

1def isBalanced(root):
2    def height(node):
3        if not node:
4            return 0
5        return 1 + max(height(node.left), height(node.right))
6
7    if not root:
8        return True
9    left_height = height(root.left)
10    right_height = height(root.right)
11    if abs(left_height - right_height) > 1:
12        return False
13    return isBalanced(root.left) and isBalanced(root.right)

Time: O(n²) — height() is called once per node, and each call visits the node's entire subtree again.
Space: O(h) — recursion stack depth equals the tree height, O(log n) average, O(n) worst case.

Approach 2 — Bottom-Up DFS with Early Exit

Instead of computing height and balance separately, do both in a single DFS pass. Return the real height when a subtree is balanced, or -1 as a sentinel the moment any imbalance is found. Parent nodes propagate -1 immediately without visiting their remaining subtree.

1. If the node is null, return 0 (base case: empty subtree has height 0).
2. Recursively compute the left subtree's height (or -1 if unbalanced).
3. If left returned -1, return -1 immediately — no need to check the right.
4. Recursively compute the right subtree's height (or -1).
5. If right returned -1, return -1.
6. If the height difference exceeds 1, return -1; otherwise return 1 + max(left, right).

1def isBalanced(root):
2    def dfs(node):
3        if not node:
4            return 0
5        left_height = dfs(node.left)
6        if left_height == -1:
7            return -1  # left subtree is already unbalanced, short-circuit
8        right_height = dfs(node.right)
9        if right_height == -1:
10            return -1  # right subtree is unbalanced
11        if abs(left_height - right_height) > 1:
12            return -1  # this node itself is unbalanced
13        return 1 + max(left_height, right_height)
14
15    return dfs(root) != -1

Time: O(n) — each node is visited exactly once, and -1 propagates upward without further recursion.
Space: O(h) — recursion stack, same as Approach 1.

Complexity Summary

Common Mistakes

• Returning height of 1 for null instead of 0 — a null node has no height; returning 1 throws off every parent's balance check by inflating both subtree heights equally, which may hide real imbalances.
• Forgetting to recurse on children in Approach 1 — confirming the root is locally balanced is not enough; the subtrees themselves must also be checked with isBalanced(root.left) && isBalanced(root.right).
• Using > 1 correctly but then flipping the sentinel — in Approach 2 the sentinel is -1 (a value no real height can take since heights are ≥ 0), so checking dfs(root) != -1 is the right final test, not dfs(root) >= 0 which is equivalent but == -1 would invert the result.
• Confusing height with depth — height is measured bottom-up (a leaf has height 1), depth is top-down (a leaf has depth equal to its level). This problem uses height; return 0 for null, not -1 in the base case.
• Using >= instead of > in the balance check — a height difference of exactly 1 is allowed; only differences greater than 1 are disqualifying.

Related Problems

• diameter-of-binary-tree — also computes heights bottom-up in a single DFS and combines results at each node
• maximum-depth-of-binary-tree — the height computation that's the core building block of this problem
• symmetric-tree — similar recursive structural check that compares left and right subtrees
• same-tree — another pairwise recursive tree comparison with the same early-exit pattern
• path-sum — recursive tree traversal that accumulates a value and checks a condition on the way back up