Balanced Binary Tree
Is the tree height-balanced — every node's subtree heights differ by at most 1?
Open on LeetCode ↗02
Intuition
Naively checking balance at each node recomputes heights repeatedly. Instead, let the height recursion itself signal failure: return −1 the moment any subtree is unbalanced, and propagate it straight up — one pass.
03
Approach
1
Height with a poison value
height(node): compute child heights; if either is −1 or they differ by > 1, return −1. Otherwise 1 + max.
2
Failure short-circuits
Once −1 appears it bubbles to the root without further real work.
3
Answer at the root
Balanced iff the root's height isn't −1.
04
Solution & live demo
python
▶1class Solution:
▶2 def isBalanced(self, root):
▶3 def height(node):
▶4 if not node: return 0
▶5 l = height(node.left)
▶6 if l == -1: return -1
▶7 r = height(node.right)
▶8 if r == -1 or abs(l - r) > 1: return -1
▶9 return 1 + max(l, r)
▶10 return height(root) != -1
05
Edge cases
Perfectly balanced but deep
Single O(n) pass — no repeated height computation.
[1,2,2,3,3,null,null,4,4]
Deep-left subtree trips the |l−r|>1 test at node 2 → −1 propagates.
06
Complexity
Time
O(n)
Space
O(h)
Single post-order pass.