Skip to main content

9. Balanced Binary Tree

easyAsked at Notion

Determine whether a binary tree is height-balanced (heights of children differ by at most 1). Notion uses this to test the single-pass DFS trick that avoids O(n^2) recomputation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion uses this to introduce the 'return -1 sentinel' optimization.
  • LeetCode Discuss (2025-09)— Reported as a quick-pivot problem in Notion phone screens.

Problem

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a tree in which the depth of the two subtrees of every node never differs by more than one.

Constraints

  • The number of nodes in the tree is in the range [0, 5000].
  • -10^4 <= Node.val <= 10^4

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
true

Example 2

Input
root = [1,2,2,3,3,null,null,4,4]
Output
false

Approaches

1. Recompute height per node

At each node, compute height of left and right; check if difference > 1.

Time
O(n^2)
Space
O(h)
function height(n) { return n ? 1 + Math.max(height(n.left), height(n.right)) : 0; }
function isBalanced(root) {
  if (!root) return true;
  if (Math.abs(height(root.left) - height(root.right)) > 1) return false;
  return isBalanced(root.left) && isBalanced(root.right);
}

Tradeoff: Naive — recomputes heights repeatedly. Quadratic on skewed trees.

2. Single-pass DFS with -1 sentinel (optimal)

Have height() return -1 if the subtree is unbalanced. At each node, if either child returns -1 or their difference > 1, return -1; else return height.

Time
O(n)
Space
O(h)
function isBalanced(root) {
  function h(n) {
    if (!n) return 0;
    const l = h(n.left);
    if (l === -1) return -1;
    const r = h(n.right);
    if (r === -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  }
  return h(root) !== -1;
}

Tradeoff: Single pass — height and balance check fused. The -1 sentinel propagates the unbalanced flag up the stack.

Notion-specific tips

Notion grades this on whether you recognize the O(n^2) trap and pivot to the single-pass sentinel trick. Articulate that you're 'piggybacking' the balance check on the height computation — that's the language they like to hear.

Common mistakes

  • Writing the O(n^2) solution and never pivoting — they want the optimization.
  • Using 0 as the sentinel — it collides with a valid empty-tree height.
  • Forgetting to short-circuit when the left subtree already returned -1.

Follow-up questions

An interviewer at Notion may pivot to one of these next:

  • Maximum Depth of Binary Tree (LC 104).
  • Diameter of Binary Tree (LC 543) — same single-pass pattern.
  • Self-balancing tree: when does AVL rebalance?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why -1 as the sentinel?

Valid heights are >= 0. Negative numbers are invalid heights, so they're unambiguous failure signals.

Could I throw an exception instead?

Yes, but exceptions for control flow are an anti-pattern in JavaScript. Sentinels keep the code linear.

Practice these live with InterviewChamp.AI

Drill Balanced Binary Tree and other Notion interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →