Balanced Binary Tree
Is the tree height-balanced — every node's subtree heights differ by at most 1?
Open on LeetCode ↗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.
The naive version computes height at every node, re-walking subtrees over and over for O(n²). The fix is a sentinel: have the height function return -1 to mean "already unbalanced below", so one post-order pass both measures and decides. Overloading a return value to carry a failure signal is a common way to collapse two traversals into one.
Approach
Height with a poison value
height(node): compute child heights; if either is −1 or they differ by > 1, return −1. Otherwise 1 + max.
Failure short-circuits
Once −1 appears it bubbles to the root without further real work.
Answer at the root
Balanced iff the root's height isn't −1.
Solution & live demo
Common pitfalls
Calling a separate height function at every node
return (abs(height(root.left) - height(root.right)) <= 1
and self.isBalanced(root.left)
and self.isBalanced(root.right))def height(node):
l = height(node.left)
if l == -1: return -1
...Each isBalanced call re-computes heights that the recursion below already knew, giving O(n²) on a skewed tree. Returning height and balance together makes it a single O(n) pass.
Checking the right subtree before short-circuiting
l = height(node.left) r = height(node.right) if l == -1 or r == -1: return -1
l = height(node.left) if l == -1: return -1 r = height(node.right)
It's still correct, but once the left side is known unbalanced the answer is settled — exploring the right subtree is wasted work. Bailing early is the point of the sentinel.
Using 0 as the failure marker
if abs(l - r) > 1: return 0
if abs(l - r) > 1: return -1
0 is the legitimate height of an empty subtree, so the parent can't distinguish failure from a null child and unbalanced trees pass. The sentinel must be a value the function could never otherwise return.
Edge cases
Single O(n) pass — no repeated height computation.
Deep-left subtree trips the |l−r|>1 test at node 2 → −1 propagates.