Loading…

easyTreesLC #110Frequently asked

Balanced Binary Tree

Q: How do you solve Balanced Binary Tree using the Top-Down — Recompute Height at Every Node (Brute) approach?

When to use it: Say it first to anchor correctness, then expose its repeated work and improve it. Showing you can spot the O(n²) is the point. The most literal translation of the definition: a tree is balanced if (a) its root's two subtree heights differ by at most 1, and (b) both subtrees are recursively balanced. **Why it's correct.** It mirrors the definition exactly, including the crucial 'every node' part — by recursing isBalanced into both children, it re-checks the height-difference condition at each node, so a deep imbalance can't slip past. **Where the waste is.** The `height()` helper walks an entire subtree to compute one number. We call it at *every* node, so the nodes near the bottom of the tree get re-traversed once for each ancestor above them. On a skewed tree of n nodes, that's roughly `n + (n-1) + ... + 1 = O(n²)` total work. The information we need — each subtree's height — is computed over and over instead of once. **The cue to optimize.** Whenever you see a helper that recomputes the same aggregate that the outer recursion is already traversing, that's a signal to *fuse* them: compute the height on the way back up and validate balance at the same time. That refactor is the optimal solution. Time complexity: O(n²). Space complexity: O(h).

Q: How do you solve Balanced Binary Tree using the Bottom-Up Height with -1 Sentinel (Optimal) approach?

When to use it: The answer they want. Frame it as 'compute height and detect imbalance in one pass, using -1 to mean unbalanced'. Fuse the two jobs the naïve version did separately. A single postorder DFS computes each subtree's height *and* validates the balance condition during the same walk, using a sentinel to carry a failure verdict upward. **The sentinel idea.** The helper normally returns a non-negative height. We overload it: return `-1` to mean 'a violation was found somewhere in this subtree'. Since a real height can never be negative, `-1` is an unambiguous failure flag that rides up the recursion for free — no separate boolean or exception needed. **The per-node logic.** Compute the left height; if it's `-1`, the left subtree is already unbalanced, so return `-1` immediately (short-circuit — don't even look right). Do the same for the right. If both children are fine, check `|leftHeight - rightHeight| > 1`: if so, *this* node is the imbalance, return `-1`. Otherwise the subtree rooted here is balanced, so return its genuine height `1 + max(left, right)` for the parent to use. **Why it's O(n).** Each node is touched once and does O(1) work, because the height it needs from its children is *returned* by the recursion rather than recomputed by a fresh traversal. The quadratic blow-up of the naïve version came entirely from re-deriving heights; computing them bottom-up exactly once removes it. **The transferable principle.** This is the classic 'compute a value and validate a property in a single pass' refactor. The same move turns Diameter of a Binary Tree, Max Path Sum, and Count Univalue Subtrees from naïve double-recursions into clean single passes — the helper returns the aggregate the parent needs while a side-channel (a sentinel, an outer variable, or a tuple) carries the answer. Time complexity: O(n). Space complexity: O(h).

LCPractice

Trees & BST · 5 of 41 · 8 min

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

In plain English

Return true only if no node anywhere violates the |leftHeight - rightHeight| ≤ 1 rule. A tree can look balanced near the top yet contain a deep, lopsided subtree — so the check must run at every node, which is exactly what makes the naïve repeated-height approach quadratic.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: true
Note: Every node's subtrees differ in height by at most 1. Root 3 has heights 1 (left) and 2 (right): difference 1.

Example 2

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Note: The left subtree grows two levels deeper than the right under node 2, violating the rule at that node even though the root looks fine at a glance.

Example 3

Input: root = []
Output: true
Note: An empty tree is vacuously balanced.

Constraints

The number of nodes is in the range [0, 5000]
-10⁴ ≤ Node.val ≤ 10⁴
An empty tree is balanced (return true)

Clarifying questions4First question: Is an empty tree considered balanced?Explore questions

Q1.Is an empty tree considered balanced?
Yes — vacuously balanced, return true. It's the base case of the recursion (height 0).
Q2.Is balance only about the root's two subtrees?
No — every node must satisfy the height-difference rule. That's the crux: a balanced root can still sit above an unbalanced subtree.
Q3.How is height defined — nodes or edges?
Either convention works as long as it's consistent, since balance compares two heights. I'll use node-count height (empty = 0, leaf = 1).
Q4.Do you want the boolean, or the offending node?
LeetCode wants a boolean. If they ask which node is unbalanced, carry the node up instead of a -1 sentinel.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A tree is height-balanced if, at EVERY node, the heights of the two subtrees differ by at most 1. The naïve solution recomputes height at every node — O(n²). The interview-grade answer is a single bottom-up (postorder) DFS that returns each subtree's height, but returns a -1 sentinel the moment it detects imbalance, short-circuiting the rest. That's O(n) time, O(h) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that the naïve top-down approach recomputes heights repeatedly (O(n²)) and can refactor to a single bottom-up pass that returns height while detecting imbalance.

Where candidates slip

Only checking balance at the root, or writing the O(n²) version that calls a separate height() function at every node, or forgetting to propagate the -1 sentinel so a deep imbalance gets lost.

How to stand out

Lead with the naïve O(n²), explain exactly where the repeated work is, then present the -1-sentinel bottom-up O(n) solution and articulate the 'fuse compute + validate' principle.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Top-Down — Recompute Height at Every Node (Brute)	`O(n²)`	`O(h)`	Say it first to anchor correctness, then expose its repeated work and improve it. Showing you can spot the O(n²) is the point.	Read
2	Bottom-Up Height with -1 Sentinel (Optimal)Optimal	`O(n)`	`O(h)`	The answer they want. Frame it as 'compute height and detect imbalance in one pass, using -1 to mean unbalanced'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewIs every node height-balanced?Compute height how often?Re-call height() at each nodeOnce, bottom-upExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Top-Down — Recompute Height at Every Node (Brute)

TimeO(n²)SpaceO(h)

Say it first to anchor correctness, then expose its repeated work and improve it. Showing you can spot the O(n²) is the point.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Start from the definition: a tree is balanced if its root's two subtree heights differ by ≤ 1 AND both subtrees are themselves balanced. How would you turn that directly into code?

2Hint 2Explore hint

Write a height() helper, then an isBalanced() that calls height(left), height(right), checks the difference, and recurses into both children.

3Hint 3Explore hint

Now count the work: height() walks an entire subtree, and you call it at every node — that's the same nodes visited over and over.

A · Core idea

The most literal translation of the definition: a tree is balanced if (a) its root's two subtree heights differ by at most 1, and (b) both subtrees are recursively balanced.

Why it's correct. It mirrors the definition exactly, including the crucial 'every node' part — by recursing isBalanced into both children, it re-checks the height-difference condition at each node, so a deep imbalance can't slip past.

Where the waste is. The height() helper walks an entire subtree to compute one number. We call it at every node, so the nodes near the bottom of the tree get re-traversed once for each ancestor above them. On a skewed tree of n nodes, that's roughly n + (n-1) + ... + 1 = O(n²) total work. The information we need — each subtree's height — is computed over and over instead of once.

The cue to optimize. Whenever you see a helper that recomputes the same aggregate that the outer recursion is already traversing, that's a signal to fuse them: compute the height on the way back up and validate balance at the same time. That refactor is the optimal solution.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,3,3,null,null,4,4]

isBalanced(root=1)

calls height(left)=3, height(right)=1

State|3-1|=2 > 1 → already false at root

Final resultfalse (but via O(n²) repeated traversals)

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full code

solution.javaJava

Top-Down — Recompute Height at Every Node (Brute) — reference

2 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public boolean isBalanced(TreeNode root) {
10
    if (root == null) return true;
11
    // Each height() call re-walks an entire subtree — the source of the O(n²) cost.
12
    int diff = Math.abs(height(root.left) - height(root.right));
13
    return diff <= 1
14
        && isBalanced(root.left)
15
        && isBalanced(root.right);
16
}
17
 
18
private int height(TreeNode node) {
19
    if (node == null) return 0;
20
    return 1 + Math.max(height(node.left), height(node.right));
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n²) timeO(h) spaceOpen the invariant and proofExplore the proof

The redundancy is structural: height() and isBalanced() traverse the same nodes, just at different times. Any time two recursions cover identical ground, fold them into one — compute the value and check the condition in a single bottom-up pass.

ComplexityO(n²) time, O(h) space — isBalanced() is called at each of the n nodes, and each call invokes height() which itself is O(size of subtree). Summed over all nodes this is O(n²) in the worst case (a skewed tree). Space is O(h) for the recursion.

E · Edge cases and pitfalls3Only checking balance at the root and skipping the recursion into children — misses deep imbalances.Explore edge cases

Pitfalls

Only checking balance at the root and skipping the recursion into children — misses deep imbalances.
Believing it's efficient because each individual function looks linear — the composition is quadratic.
Not recognizing the repeated traversal as the thing to optimize.

03.2

Approach 2 of 2 · Optimal

Bottom-Up Height with -1 Sentinel (Optimal)

TimeO(n)SpaceO(h)

The answer they want. Frame it as 'compute height and detect imbalance in one pass, using -1 to mean unbalanced'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The naïve version recomputes height everywhere. What if a single recursion returned the height AND signaled imbalance at the same time?

2Hint 2Explore hint

Have the helper return the subtree's height normally, but return a special value like -1 the moment it discovers any imbalance below it.

3Hint 3Explore hint

At each node: get left and right heights; if either is -1, or they differ by more than 1, return -1. Otherwise return 1 + max(left, right). The root is balanced iff the helper doesn't return -1.

A · Core idea

Fuse the two jobs the naïve version did separately. A single postorder DFS computes each subtree's height and validates the balance condition during the same walk, using a sentinel to carry a failure verdict upward.

The sentinel idea. The helper normally returns a non-negative height. We overload it: return -1 to mean 'a violation was found somewhere in this subtree'. Since a real height can never be negative, -1 is an unambiguous failure flag that rides up the recursion for free — no separate boolean or exception needed.

The per-node logic. Compute the left height; if it's -1, the left subtree is already unbalanced, so return -1 immediately (short-circuit — don't even look right). Do the same for the right. If both children are fine, check |leftHeight - rightHeight| > 1: if so, this node is the imbalance, return -1. Otherwise the subtree rooted here is balanced, so return its genuine height 1 + max(left, right) for the parent to use.

Why it's O(n). Each node is touched once and does O(1) work, because the height it needs from its children is returned by the recursion rather than recomputed by a fresh traversal. The quadratic blow-up of the naïve version came entirely from re-deriving heights; computing them bottom-up exactly once removes it.

The transferable principle. This is the classic 'compute a value and validate a property in a single pass' refactor. The same move turns Diameter of a Binary Tree, Max Path Sum, and Count Univalue Subtrees from naïve double-recursions into clean single passes — the helper returns the aggregate the parent needs while a side-channel (a sentinel, an outer variable, or a tuple) carries the answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,3,3,null,null,4,4] (left side two levels deeper)

Interactive diagram

Heights bubbling up, root poisoned to -1

height(4) leaves

Active call / nodeSupporting contextReturned stateNot active

The left subtree reaches height 3, the right height 1; |3-1|=2 forces the root to return -1.

Final resultfalse

C · Code with teaching comments

solution.javaJava

Bottom-Up Height with -1 Sentinel (Optimal) — optimal

4 teaching notes

1
public boolean isBalanced(TreeNode root) {
2
    // The whole tree is balanced exactly when the helper never poisoned the height to
3
    // -1.
4
    return height(root) != -1;
5
}
6
 
7
private int height(TreeNode node) {
8
    if (node == null) return 0;                 // empty subtree
9
    int left = height(node.left);
10
    if (left == -1) return -1;                  // short-circuit: left already bad
11
    int right = height(node.right);
12
    if (right == -1) return -1;                 // short-circuit: right already bad
13
    if (Math.abs(left - right) > 1) return -1;  // THIS node is unbalanced
14
    return 1 + Math.max(left, right);           // balanced → real height
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Overloading a numeric return with an impossible value (-1 for a quantity that's normally ≥ 0) is a tidy way to smuggle a boolean verdict through a recursion that's already returning a number. It avoids a second pass and a second data channel — one return value does double duty.

ComplexityO(n) time, O(h) space — Each node is visited exactly once: the height is computed on the way back up, and the balance check is O(1) per node → O(n) total time. Recursion depth is the tree height h → O(h) space. The -1 short-circuit can only make it faster, never slower.

E · Edge cases and pitfalls6root = [] — height(null) = 0, and 0 != -1 → returns true (empty tree is balanced).Explore edge cases

Edge cases handled

root = []height(null) = 0, and 0 != -1 → returns true (empty tree is balanced).
root = [1]height = 1, not -1 → true.
Perfectly skewed tree of 3+ nodesFirst node where the height difference exceeds 1 returns -1, which short-circuits all ancestors → false in one pass.

Pitfalls

Forgetting to short-circuit on a child's -1 — you'd do extra work and could mis-handle the sentinel as a real height.
Treating -1 as a valid height in the max/+1 arithmetic — always check for it before using the value.
Using > vs >= incorrectly in the |left - right| test — the rule is 'differ by at most 1', so fail only when the difference exceeds 1.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isBalanced(TreeNode root) { return height(root) != -1; } private int height(TreeNode node) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Only checking the root's two subtrees

A balanced root can sit above a deeply unbalanced subtree. Balance must hold at EVERY node, so the recursion has to validate each one.

Explore the code comparison

Don't write this

def isBalanced(self, root):
    if not root:
        return True
    return abs(self.height(root.left) - self.height(root.right)) <= 1
    # never checks the children's own balance

Write this instead

def isBalanced(self, root):
    def height(node):
        if not node:
            return 0
        l = height(node.left)
        if l == -1: return -1
        r = height(node.right)
        if r == -1: return -1
        if abs(l - r) > 1: return -1
        return 1 + max(l, r)
    return height(root) != -1

Quadratic recompute of heights

Calling a standalone height() at every node re-walks overlapping subtrees, giving O(n²). Compute the height once on the way up and check balance during the same pass.

Explore the code comparison

Don't write this

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1
        && isBalanced(root.left) && isBalanced(root.right);  // height() re-run everywhere
}

Write this instead

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
private int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left);  if (l == -1) return -1;
    int r = height(node.right); if (r == -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bottom-up height DFS with a -1 sentinel for 'unbalanced'

Code pattern to memorize

height(node):
    if node is null: return 0
    L = height(node.left);  if L == -1: return -1
    R = height(node.right); if R == -1: return -1
    if |L - R| > 1: return -1   # unbalanced → poison upward
    return 1 + max(L, R)

Rules to remember

1Balance is checked at every node, not just the root — a balanced root can still hide a deep imbalance below.
2Naïve = compute height at each node separately → O(n²). The fix is to compute height once, bottom-up.
3Use -1 as a sentinel meaning 'this subtree is already unbalanced' so the imbalance propagates up without extra flags.
4Short-circuit: the instant a child returns -1, return -1 immediately — don't keep recursing.
5Empty subtree height = 0; balance condition is |leftHeight - rightHeight| ≤ 1.

Use this pattern when

You must verify a per-node structural property that depends on subtree heights
You want to compute a value and validate a condition in a single pass (fuse them)
Avoiding repeated work that an O(n²) recompute-from-scratch would cause

Choose another pattern when

You only need the height, with no balance check → plain Maximum Depth
The condition is global ordering, not height → Validate BST's bounds DFS
You need the actual unbalanced node, not a boolean → carry the node, not a sentinel

Interview takeaway

The lesson is fusing computation with validation. Instead of computing height and checking balance in two separate passes (O(n²)), do both in one postorder traversal and use a sentinel value to carry the failure verdict upward. That 'compute-and-check in one pass with a sentinel' trick recurs across tree problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFuse computation with validation in one bottom-up (postorder) pass, using a sentinel value to carry a failure verdict upward. This converts naïve O(n²) 'recompute an aggregate at every node' solutions into O(n). The same refactor powers Diameter, Max Path Sum, and Count Univalue Subtrees.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Depth of Binary Tree
The plain height recursion this problem builds on — no balance check, just 1 + max(left, right).
Diameter of Binary Tree
Same bottom-up height pass, but track leftHeight + rightHeight to find the longest path through any node.
Binary Tree Maximum Path Sum
Helper returns the best downward path sum; an outer variable captures the best through-node sum — same fuse pattern.
Balance a Binary Search Tree
Coming soon
Inorder to a sorted array, then rebuild by recursively picking the middle as root.

Same pattern

←

Maximum Depth of Binary Tree

Continue · Next problem

Same Tree

easyTreesLC #110Frequently asked

Balanced Binary Tree

LCPractice

Trees & BST · 5 of 41 · 8 min

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

In plain English

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: true
Note: Every node's subtrees differ in height by at most 1. Root 3 has heights 1 (left) and 2 (right): difference 1.

Example 2

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Note: The left subtree grows two levels deeper than the right under node 2, violating the rule at that node even though the root looks fine at a glance.

Example 3

Input: root = []
Output: true
Note: An empty tree is vacuously balanced.

Constraints

The number of nodes is in the range [0, 5000]
-10⁴ ≤ Node.val ≤ 10⁴
An empty tree is balanced (return true)

Clarifying questions4First question: Is an empty tree considered balanced?Explore questions

Q1.Is an empty tree considered balanced?
Yes — vacuously balanced, return true. It's the base case of the recursion (height 0).
Q2.Is balance only about the root's two subtrees?
No — every node must satisfy the height-difference rule. That's the crux: a balanced root can still sit above an unbalanced subtree.
Q3.How is height defined — nodes or edges?
Either convention works as long as it's consistent, since balance compares two heights. I'll use node-count height (empty = 0, leaf = 1).
Q4.Do you want the boolean, or the offending node?
LeetCode wants a boolean. If they ask which node is unbalanced, carry the node up instead of a -1 sentinel.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that the naïve top-down approach recomputes heights repeatedly (O(n²)) and can refactor to a single bottom-up pass that returns height while detecting imbalance.

Where candidates slip

Only checking balance at the root, or writing the O(n²) version that calls a separate height() function at every node, or forgetting to propagate the -1 sentinel so a deep imbalance gets lost.

How to stand out

Lead with the naïve O(n²), explain exactly where the repeated work is, then present the -1-sentinel bottom-up O(n) solution and articulate the 'fuse compute + validate' principle.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Top-Down — Recompute Height at Every Node (Brute)	`O(n²)`	`O(h)`	Say it first to anchor correctness, then expose its repeated work and improve it. Showing you can spot the O(n²) is the point.	Read
2	Bottom-Up Height with -1 Sentinel (Optimal)Optimal	`O(n)`	`O(h)`	The answer they want. Frame it as 'compute height and detect imbalance in one pass, using -1 to mean unbalanced'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Top-Down — Recompute Height at Every Node (Brute)

TimeO(n²)SpaceO(h)

Say it first to anchor correctness, then expose its repeated work and improve it. Showing you can spot the O(n²) is the point.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Start from the definition: a tree is balanced if its root's two subtree heights differ by ≤ 1 AND both subtrees are themselves balanced. How would you turn that directly into code?

2Hint 2Explore hint

Write a height() helper, then an isBalanced() that calls height(left), height(right), checks the difference, and recurses into both children.

3Hint 3Explore hint

Now count the work: height() walks an entire subtree, and you call it at every node — that's the same nodes visited over and over.

A · Core idea

The most literal translation of the definition: a tree is balanced if (a) its root's two subtree heights differ by at most 1, and (b) both subtrees are recursively balanced.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,3,3,null,null,4,4]

isBalanced(root=1)

calls height(left)=3, height(right)=1

State|3-1|=2 > 1 → already false at root

Final resultfalse (but via O(n²) repeated traversals)

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full code

solution.javaJava

Top-Down — Recompute Height at Every Node (Brute) — reference

2 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public boolean isBalanced(TreeNode root) {
10
    if (root == null) return true;
11
    // Each height() call re-walks an entire subtree — the source of the O(n²) cost.
12
    int diff = Math.abs(height(root.left) - height(root.right));
13
    return diff <= 1
14
        && isBalanced(root.left)
15
        && isBalanced(root.right);
16
}
17
 
18
private int height(TreeNode node) {
19
    if (node == null) return 0;
20
    return 1 + Math.max(height(node.left), height(node.right));
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n²) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Only checking balance at the root and skipping the recursion into children — misses deep imbalances.Explore edge cases

Pitfalls

Only checking balance at the root and skipping the recursion into children — misses deep imbalances.
Believing it's efficient because each individual function looks linear — the composition is quadratic.
Not recognizing the repeated traversal as the thing to optimize.

03.2

Approach 2 of 2 · Optimal

Bottom-Up Height with -1 Sentinel (Optimal)

TimeO(n)SpaceO(h)

The answer they want. Frame it as 'compute height and detect imbalance in one pass, using -1 to mean unbalanced'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The naïve version recomputes height everywhere. What if a single recursion returned the height AND signaled imbalance at the same time?

2Hint 2Explore hint

Have the helper return the subtree's height normally, but return a special value like -1 the moment it discovers any imbalance below it.

3Hint 3Explore hint

At each node: get left and right heights; if either is -1, or they differ by more than 1, return -1. Otherwise return 1 + max(left, right). The root is balanced iff the helper doesn't return -1.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,3,3,null,null,4,4] (left side two levels deeper)

Interactive diagram

Heights bubbling up, root poisoned to -1

height(4) leaves

Active call / nodeSupporting contextReturned stateNot active

The left subtree reaches height 3, the right height 1; |3-1|=2 forces the root to return -1.

Final resultfalse

C · Code with teaching comments

solution.javaJava

Bottom-Up Height with -1 Sentinel (Optimal) — optimal

4 teaching notes

1
public boolean isBalanced(TreeNode root) {
2
    // The whole tree is balanced exactly when the helper never poisoned the height to
3
    // -1.
4
    return height(root) != -1;
5
}
6
 
7
private int height(TreeNode node) {
8
    if (node == null) return 0;                 // empty subtree
9
    int left = height(node.left);
10
    if (left == -1) return -1;                  // short-circuit: left already bad
11
    int right = height(node.right);
12
    if (right == -1) return -1;                 // short-circuit: right already bad
13
    if (Math.abs(left - right) > 1) return -1;  // THIS node is unbalanced
14
    return 1 + Math.max(left, right);           // balanced → real height
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6root = [] — height(null) = 0, and 0 != -1 → returns true (empty tree is balanced).Explore edge cases

Edge cases handled

root = []height(null) = 0, and 0 != -1 → returns true (empty tree is balanced).
root = [1]height = 1, not -1 → true.
Perfectly skewed tree of 3+ nodesFirst node where the height difference exceeds 1 returns -1, which short-circuits all ancestors → false in one pass.

Pitfalls

Forgetting to short-circuit on a child's -1 — you'd do extra work and could mis-handle the sentinel as a real height.
Treating -1 as a valid height in the max/+1 arithmetic — always check for it before using the value.
Using > vs >= incorrectly in the |left - right| test — the rule is 'differ by at most 1', so fail only when the difference exceeds 1.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isBalanced(TreeNode root) { return height(root) != -1; } private int height(TreeNode node) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Only checking the root's two subtrees

A balanced root can sit above a deeply unbalanced subtree. Balance must hold at EVERY node, so the recursion has to validate each one.

Explore the code comparison

Don't write this

def isBalanced(self, root):
    if not root:
        return True
    return abs(self.height(root.left) - self.height(root.right)) <= 1
    # never checks the children's own balance

Write this instead

def isBalanced(self, root):
    def height(node):
        if not node:
            return 0
        l = height(node.left)
        if l == -1: return -1
        r = height(node.right)
        if r == -1: return -1
        if abs(l - r) > 1: return -1
        return 1 + max(l, r)
    return height(root) != -1

Quadratic recompute of heights

Calling a standalone height() at every node re-walks overlapping subtrees, giving O(n²). Compute the height once on the way up and check balance during the same pass.

Explore the code comparison

Don't write this

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1
        && isBalanced(root.left) && isBalanced(root.right);  // height() re-run everywhere
}

Write this instead

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}
private int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left);  if (l == -1) return -1;
    int r = height(node.right); if (r == -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bottom-up height DFS with a -1 sentinel for 'unbalanced'

Code pattern to memorize

height(node):
    if node is null: return 0
    L = height(node.left);  if L == -1: return -1
    R = height(node.right); if R == -1: return -1
    if |L - R| > 1: return -1   # unbalanced → poison upward
    return 1 + max(L, R)

Rules to remember

1Balance is checked at every node, not just the root — a balanced root can still hide a deep imbalance below.
2Naïve = compute height at each node separately → O(n²). The fix is to compute height once, bottom-up.
3Use -1 as a sentinel meaning 'this subtree is already unbalanced' so the imbalance propagates up without extra flags.
4Short-circuit: the instant a child returns -1, return -1 immediately — don't keep recursing.
5Empty subtree height = 0; balance condition is |leftHeight - rightHeight| ≤ 1.

Use this pattern when

You must verify a per-node structural property that depends on subtree heights
You want to compute a value and validate a condition in a single pass (fuse them)
Avoiding repeated work that an O(n²) recompute-from-scratch would cause

Choose another pattern when

You only need the height, with no balance check → plain Maximum Depth
The condition is global ordering, not height → Validate BST's bounds DFS
You need the actual unbalanced node, not a boolean → carry the node, not a sentinel

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Depth of Binary Tree
The plain height recursion this problem builds on — no balance check, just 1 + max(left, right).
Diameter of Binary Tree
Same bottom-up height pass, but track leftHeight + rightHeight to find the longest path through any node.
Binary Tree Maximum Path Sum
Helper returns the best downward path sum; an outer variable captures the best through-node sum — same fuse pattern.
Balance a Binary Search Tree
Coming soon
Inorder to a sorted array, then rebuild by recursively picking the middle as root.

Same pattern

←

Maximum Depth of Binary Tree

Continue · Next problem

Same Tree