Balanced Binary Tree (LeetCode 110)
You're given a binary tree and need to decide whether it counts as height-balanced.
A tree earns that label when, at every single node, the heights of its left and right subtrees never disagree by more than one.
Worked Examples
root = [3,9,20,null,null,15,7]trueroot = [1,2,2,3,3,null,null,4,4]falseroot = []true⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 5000].-104 <= Node.val <= 104
Core Insight
Returning -1 from subtrees allows instant failure propagation without computing full tree depths.
Real-World Scenario & Production Applications
Self-balancing AVL/Red-Black tree rebalancing triggers, database index tree verification.
Step-by-Step Execution Trace Table
| Node | Left Height | Right Height | Difference | Status |
|---|---|---|---|---|
| 15 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 7 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 20 | 1 | 1 | 0 | Balanced (h=2) |
| 9 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 3 (root) | 1 | 2 | 1 | Balanced (h=3) |
root = [3,9,20,null,null,15,7]true| Node | Left Height | Right Height | Difference | Status |
|---|---|---|---|---|
| 15 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 7 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 20 | 1 | 1 | 0 | Balanced (h=2) |
| 9 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 3 (root) | 1 | 2 | 1 | Balanced (h=3) |
| 1 | def check_height(node): |
| 2 | if not node: |
| 3 | return 0 |
| 4 | left, right = check_height(node.left), check_height(node.right) |
| 5 | if left == -1 or right == -1 or abs(left - right) > 1: |
| 6 | return -1 |
| 7 | return max(left, right) + 1 |
| 8 | return check_height(root) != -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The obvious approach — compute each subtree's height, then separately check balance at each node — re-walks the same subtrees over and over. This trick answers both questions in a single pass by hijacking the return value.
🏗️ The Analogy: A Building Inspector Who Stops at the First Crack
Imagine a building inspector checking a tower floor by floor, from the top down conceptually, but reporting bottom-up. At each floor, they want to report how tall the tower is above this point — but if they ever discover a structural imbalance below, there's no point continuing to measure heights accurately; they just need to report "unsafe" all the way up to whoever's asking, instantly, without finishing the inspection.
🔑 The Key Idea in the Code
-1 is overloaded to mean two different things depending on context: "not yet checked" becomes "structurally broken, stop caring about the real number." Once any subtree reports -1, every ancestor just relays -1 straight up without doing any more work — a free early exit riding on the same recursive call that computes height.
Quadratic top-down traversal: Calling
height(node.left)andheight(node.right)at each level recomputes subtree depths redundantly. A bottom-up DFS returning-1on imbalance computes balance in time.Missing sentinel early-exit propagation: When a child subtree returns
-1(unbalanced), the parent must immediately propagate-1without computingabs(left - right).Treating difference of 1 as unbalanced: The definition of height-balanced requires
abs(left - right) <= 1. Failing when difference equals 1 rejects valid balanced trees.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Tree height-balance condition + require optimal O(N) single-pass without quadratic depth recalculations.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: check_height returns actual subtree height if balanced, or -1 if any descendant subtree is unbalanced.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to check if
left_h == -1before checking right subtree.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use a bottom-up post-order DFS helper
check_height. It returns the height if balanced, or -1 as soon as any subtree is unbalanced. When a child returns -1 or abs(L - R) > 1, it immediately propagates -1 upward. Runs in strictO(N)time and O(H) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Bottom-up DFS returns tree height or -1 if unbalanced. Any unbalanced subtree short-circuits immediately, visiting each node at most once.
O(H) Auxiliary
Recursion stack depth equals tree height H.
T(N) = ∑_{v} O(1) = O(N)
Derivation Progression
H(v) = 1 + max(HL, HR)
Computes height from children in a single post-order traversal.
if |HL - HR| > 1: return -1
Propagates failure upward immediately without redundant visits.
O(N) node visits
Eliminates repeated depth calculations.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack (log N <= H <= N)
O(1) Zero heap memory
O(1) Boolean balance status
Boundary Best / Worst Cases
if root is unbalanced, otherwise .
.
on balanced tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "height-balanced binary tree", "depth of two subtrees of every node never differs by more than one". Naive top-down calculation computes depth(left) and depth(right) at each node, taking time. A Senior SWE implements a Bottom-Up Check with Sentinel Early Exit (-1): return actual height if balanced, or -1 if unbalanced to immediately short-circuit up the call stack!
. Time budget is strictly linear time.
top-down trap: calling maxDepth inside a separate isBalanced recursive helper causes redundant traversal. The combined height/balance check solves the entire problem in a single post-order pass.
Balanced Binary Tree (LeetCode 110)
You're given a binary tree and need to decide whether it counts as height-balanced.
A tree earns that label when, at every single node, the heights of its left and right subtrees never disagree by more than one.
Worked Examples
root = [3,9,20,null,null,15,7]trueroot = [1,2,2,3,3,null,null,4,4]falseroot = []true⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 5000].-104 <= Node.val <= 104
Core Insight
Returning -1 from subtrees allows instant failure propagation without computing full tree depths.
Real-World Scenario & Production Applications
Self-balancing AVL/Red-Black tree rebalancing triggers, database index tree verification.
Step-by-Step Execution Trace Table
| Node | Left Height | Right Height | Difference | Status |
|---|---|---|---|---|
| 15 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 7 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 20 | 1 | 1 | 0 | Balanced (h=2) |
| 9 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 3 (root) | 1 | 2 | 1 | Balanced (h=3) |
root = [3,9,20,null,null,15,7]true| Node | Left Height | Right Height | Difference | Status |
|---|---|---|---|---|
| 15 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 7 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 20 | 1 | 1 | 0 | Balanced (h=2) |
| 9 (leaf) | 0 | 0 | 0 | Balanced (h=1) |
| 3 (root) | 1 | 2 | 1 | Balanced (h=3) |
| 1 | def check_height(node): |
| 2 | if not node: |
| 3 | return 0 |
| 4 | left, right = check_height(node.left), check_height(node.right) |
| 5 | if left == -1 or right == -1 or abs(left - right) > 1: |
| 6 | return -1 |
| 7 | return max(left, right) + 1 |
| 8 | return check_height(root) != -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The obvious approach — compute each subtree's height, then separately check balance at each node — re-walks the same subtrees over and over. This trick answers both questions in a single pass by hijacking the return value.
🏗️ The Analogy: A Building Inspector Who Stops at the First Crack
Imagine a building inspector checking a tower floor by floor, from the top down conceptually, but reporting bottom-up. At each floor, they want to report how tall the tower is above this point — but if they ever discover a structural imbalance below, there's no point continuing to measure heights accurately; they just need to report "unsafe" all the way up to whoever's asking, instantly, without finishing the inspection.
🔑 The Key Idea in the Code
-1 is overloaded to mean two different things depending on context: "not yet checked" becomes "structurally broken, stop caring about the real number." Once any subtree reports -1, every ancestor just relays -1 straight up without doing any more work — a free early exit riding on the same recursive call that computes height.
Quadratic top-down traversal: Calling
height(node.left)andheight(node.right)at each level recomputes subtree depths redundantly. A bottom-up DFS returning-1on imbalance computes balance in time.Missing sentinel early-exit propagation: When a child subtree returns
-1(unbalanced), the parent must immediately propagate-1without computingabs(left - right).Treating difference of 1 as unbalanced: The definition of height-balanced requires
abs(left - right) <= 1. Failing when difference equals 1 rejects valid balanced trees.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Tree height-balance condition + require optimal O(N) single-pass without quadratic depth recalculations.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: check_height returns actual subtree height if balanced, or -1 if any descendant subtree is unbalanced.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to check if
left_h == -1before checking right subtree.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use a bottom-up post-order DFS helper
check_height. It returns the height if balanced, or -1 as soon as any subtree is unbalanced. When a child returns -1 or abs(L - R) > 1, it immediately propagates -1 upward. Runs in strictO(N)time and O(H) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Bottom-up DFS returns tree height or -1 if unbalanced. Any unbalanced subtree short-circuits immediately, visiting each node at most once.
O(H) Auxiliary
Recursion stack depth equals tree height H.
T(N) = ∑_{v} O(1) = O(N)
Derivation Progression
H(v) = 1 + max(HL, HR)
Computes height from children in a single post-order traversal.
if |HL - HR| > 1: return -1
Propagates failure upward immediately without redundant visits.
O(N) node visits
Eliminates repeated depth calculations.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack (log N <= H <= N)
O(1) Zero heap memory
O(1) Boolean balance status
Boundary Best / Worst Cases
if root is unbalanced, otherwise .
.
on balanced tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "height-balanced binary tree", "depth of two subtrees of every node never differs by more than one". Naive top-down calculation computes depth(left) and depth(right) at each node, taking time. A Senior SWE implements a Bottom-Up Check with Sentinel Early Exit (-1): return actual height if balanced, or -1 if unbalanced to immediately short-circuit up the call stack!
. Time budget is strictly linear time.
top-down trap: calling maxDepth inside a separate isBalanced recursive helper causes redundant traversal. The combined height/balance check solves the entire problem in a single post-order pass.