Trees crash course ↗ · 144

110. Balanced Binary Tree

A binary tree is height-balanced when every node's left and right subtrees differ in height by at most 1. The trick is to compute height and detect imbalance in one post-order DFS pass, propagating a -1 sentinel the moment any subtree is off — no redundant traversals.

● EasyPost-order DFSSentinel ValueTree HeightTypeScript

PROBLEM What we're solving

Given the root of a binary tree, return true if the tree is height-balanced: for every node, the heights of its left and right subtrees differ by at most 1.

Worked example. Tree 3,9,20,null,null,15,7 (level-order):

Node 3: left height = 1, right height = 2, difference = 1 ✓. Both subtrees rooted at 20 have height 1. Every node passes → return true.

Contrast with 1,2,2,3,3,null,null,4,4: the leftmost path reaches depth 4 while the right side only reaches depth 2 → return false.

KEY IDEA Return height — or a sentinel when unbalanced

Insight → a post-order DFS that returns the height of each subtree already has everything it needs to detect imbalance. When a subtree is unbalanced, return -1 as a sentinel instead of the real height. Every ancestor that sees -1 immediately propagates it upward — no second traversal, no global flag. One pass, O(n) total work.

RECIPE Post-order DFS with the −1 sentinel

0 · Base case. null node returns 0 — an empty tree has height zero and is trivially balanced.
1 · Recurse left. Call dfs(node.left). If it returns -1, short-circuit and return -1 immediately — no point checking the right subtree.
2 · Recurse right. Call dfs(node.right). Same fast-path on -1.
3 · Check balance at this node. If |leftH − rightH| > 1, return -1.
4 · Return true height. 1 + Math.max(leftH, rightH). This value is what the parent will receive.
5 · Outer call. isBalanced returns dfs(root) !== -1.

Classic confusion → many people write a naive two-function solution: isBalanced calls height(node.left) and height(node.right) per node, then recurses into both children. That recomputes heights from scratch for every node, giving O(n²) worst-case on a skewed tree. The sentinel trick merges both jobs into one DFS pass.

COST Complexity & alternatives

Naive: isBalanced + separate height()

O(n²)

height() is called once per node from isBalanced, each walking a subtree.

Sentinel DFS (one pass)

O(n)

Each node visited exactly once; O(h) call stack space where h = tree height.

Space note

The implicit call stack uses O(h) space: O(log n) for a balanced tree, O(n) for a fully skewed one. An iterative post-order with an explicit stack avoids stack-overflow risk on very deep inputs but adds implementation complexity.

Pattern transfer →the "return height or sentinel" pattern applies directly to Diameter of Binary Tree (return depth, track max diameter as a side effect), Binary Tree Maximum Path Sum (return max gain upward, track global max), and Lowest Common Ancestor (return the LCA node up the call stack once found).

RUN IT Post-order DFS — return height or −1 sentinel

Tree (level-order):

step 0 / 16

STARTStarting post-order DFS from the root. We'll return the height from each subtree, or -1as an "unbalanced" sentinel.

1▶function isBalanced(root: TreeNode | null): boolean {
2▶  function dfs(node: TreeNode | null): number {
3    if (node === null) return 0;           // base case: empty tree has height 0
4 
5    const leftH = dfs(node.left);
6    if (leftH === -1) return -1;           // fast-path: left already unbalanced
7 
8    const rightH = dfs(node.right);
9    if (rightH === -1) return -1;          // fast-path: right already unbalanced
10 
11    if (Math.abs(leftH - rightH) > 1) return -1;  // this node is unbalanced
12 
13    return 1 + Math.max(leftH, rightH);   // balanced; return true height
14  }
15 
16  return dfs(root) !== -1;
17}

State

null

node

—

leftH

—

rightH

—

height

(empty)

call stack

current nodeon call stackbalanced subtreeunbalanced (sentinel −1)

slowfast

TYPESCRIPT The solution, annotated

isBalanced.ts
function isBalanced(root: TreeNode | null): boolean {
  function dfs(node: TreeNode | null): number {
    if (node === null) return 0;           // base case: empty tree has height 0

    const leftH = dfs(node.left);
    if (leftH === -1) return -1;           // fast-path: left already unbalanced

    const rightH = dfs(node.right);
    if (rightH === -1) return -1;          // fast-path: right already unbalanced

    if (Math.abs(leftH - rightH) > 1) return -1;  // this node is unbalanced

    return 1 + Math.max(leftH, rightH);   // balanced; return true height
  }

  return dfs(root) !== -1;
}

Reading it block by block

Lines 2–3 — base case. A null node contributes height 0 and is always balanced. Returning 0 (not −1) lets the parent count correctly.

Lines 5–6 — left subtree fast-path. Recurse left first (post-order). If the returned value is -1, the subtree is already unbalanced — short-circuit immediately. This is what makes the overall pass O(n): once we see the sentinel we never visit more nodes on that branch.

Lines 8–9 — right subtree fast-path. Same logic for the right child. Both fast-paths together ensure we stop work the instant any subtree is invalid.

Line 11 — balance check. With both heights now available and both known to be non-sentinel, we check |leftH − rightH| > 1. This is the core predicate; returning -1 here propagates the failure upward through all ancestors.

Line 13 — return true height. 1 + Math.max(leftH, rightH) is the standard recursive height formula. The parent will use this value in its own balance check.

Line 16 — outer wrapper. Any non-negative return means the whole tree is balanced. We test dfs(root) !== -1 to convert the height/sentinel result to a boolean.

Complexity → O(n) time — each node is visited exactly once in the post-order traversal. O(h) space for the call stack, where h is the tree height (O(log n) balanced, O(n) skewed).

INTERVIEWFollow-ups they'll ask

"Can you do it iteratively?" Yes — iterative post-order with an explicit stack. Push nodes, process after both children are done; maintain a height map. Avoids stack-overflow on deep trees but adds ~15 lines.
"What if the tree is very deep / could stack-overflow?" Use the iterative approach above, or check process.setMaxCallStackSize in Node. In an interview, mention the risk and offer the iterative alternative.
"How would you return the unbalanced node, not just true/false?" Instead of -1, return the node itself (or its value) when unbalanced, and a sentinel object for "balanced with height h".
"Related: Diameter of Binary Tree (LC 543)?" Track a maxDiameter variable in the outer scope; update it with leftH + rightH at each node while still returning the true height upward.
"What's the naive O(n²) approach and why is it worse?" Call a separate height() function for every node inside isBalanced. Each height() call walks a subtree, so nodes near the root are visited O(n) times each.

OPTIMAL Post-order DFS

isBalanced.ts
function isBalanced(root: TreeNode | null): boolean {
  function dfs(node: TreeNode | null): number {
    if (node === null) return 0;           // base case: empty tree has height 0

    const leftH = dfs(node.left);
    if (leftH === -1) return -1;           // fast-path: left already unbalanced

    const rightH = dfs(node.right);
    if (rightH === -1) return -1;          // fast-path: right already unbalanced

    if (Math.abs(leftH - rightH) > 1) return -1;  // this node is unbalanced

    return 1 + Math.max(leftH, rightH);   // balanced; return true height
  }

  return dfs(root) !== -1;
}

Complexity → O(n) time — each node is visited exactly once in the post-order traversal. O(h) space for the call stack, where h is the tree height (O(log n) balanced, O(n) skewed).

ALT 1 Brute force — recompute height at every node

O(n²) time · O(n) space

At each node, independently compute the height of the left and right subtrees with a helper, check that they differ by at most one, then recurse into both children — the literal translation of the definition before you notice the heights can be reused.

approach-2.ts
function isBalanced(root: TreeNode | null): boolean {
  function height(node: TreeNode | null): number {
    if (node === null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
  }

  if (root === null) return true;
  if (Math.abs(height(root.left) - height(root.right)) > 1) return false;
  return isBalanced(root.left) && isBalanced(root.right);
}

Note → heightwalks each subtree from scratch on every visit, so a skewed tree does O(n) work at each of O(n) nodes — O(n²) overall. Returning -1 from a single bottom-up pass reuses the heights you already computed and brings it down to O(n).

MNEMONIC The one-liner

"Post-order: children report their heights first, then the parent checks the gap. If the gap is too big, swap the real height for −1 and let it bubble up."

TRIGGERS When you see _ → reach for _

"is the tree balanced / height-balanced"	post-order DFS returning height or −1 sentinel
need height AND a validity check in one pass	merge both into the return value: real height OR sentinel
recursive result that short-circuits on bad subtree	check sentinel immediately after each recursive call
"diameter / max path sum" (same shape)	track side-effect in outer variable; return height upward

SKELETON The reusable shape

skeleton.ts
function isBalanced(root: TreeNode | null): boolean {
  function dfs(node: TreeNode | null): number {
    if (node === null) return 0;
    const L = dfs(node.left);
    if (L === -1) return -1;
    const R = dfs(node.right);
    if (R === -1) return -1;
    if (Math.abs(L - R) > 1) return -1;
    return 1 + Math.max(L, R);
  }
  return dfs(root) !== -1;
}

FLASHCARDS Tap to flip

What does the inner DFS function return?

The height of the subtree, or -1 if any subtree rooted at or below the current node is unbalanced.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the one-pass sentinel DFS?

QUESTION 02

For the tree 3,9,20,null,null,15,7, what does isBalanced return?

QUESTION 03

What does the inner DFS return when a null node is reached?

QUESTION 04

Why does the sentinel DFS short-circuit after the left child returns −1?

QUESTION 05

The naive approach calls a separate height() function inside isBalanced. What's wrong with it?

QUESTION 06

What does isBalanced(root) return if dfs(root) returns 3?

QUESTION 07

Which sibling problem is solved by the same "return height, track side-effect" pattern?

QUESTION 08

#110 · Balanced Binary TreePost-order DFS returns the subtree height, propagating a −1 sentinel the moment any sibling pair differs by more than one — short-circuiting the rest of the traversal immediately.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Return height — or a sentinel when unbalanced

RECIPE Post-order DFS with the −1 sentinel

COST Complexity & alternatives

Space note

RUN IT Post-order DFS — return height or −1 sentinel

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Post-order DFS

ALT 1 Brute force — recompute height at every node

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _