Skip to main content

14. Balanced Binary Tree

easyAsked at Coinbase

Determine if a binary tree is height-balanced. Coinbase uses this to test the post-order short-circuit pattern — the same trick used to validate constraints across an order-book tree.

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

Source citations

Public interview reports confirming this problem appears in Coinbase loops.

  • Glassdoor (2026-Q1)— Coinbase backend onsite.

Problem

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is one 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. Compute height per node

At each node, compute heights of both subtrees independently; check |diff| <= 1.

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

Tradeoff: Quadratic because h() is recomputed at every level. Mention only as the warm-up.

2. Single-pass DFS returning height-or-fail

Recurse and return the subtree height, but return -1 to signal 'unbalanced'. Short-circuit up the call stack.

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

Tradeoff: Linear because each node is visited once. The -1 sentinel is the classic 'fail fast in a recursive computation' trick.

Coinbase-specific tips

Coinbase grades the single-pass with sentinel return — they want to see you can encode 'value or fail' in one return type. Mention the alternative of returning a tuple {height, balanced} — both valid; sentinel is slightly faster. The skill transfers to validating any tree-shaped invariant in one pass.

Common mistakes

  • Computing height twice (recompute-at-each-node pattern) — O(n^2).
  • Returning a tuple in a language without easy multi-return — pick the sentinel instead.
  • Forgetting to short-circuit — checking both children even after the left returned -1.

Follow-up questions

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

  • Make the tree balanced — rotation algorithms (AVL).
  • What if 'balanced' means '|count(left) - count(right)| <= 1' instead of heights?
  • Iterative variant with explicit stack.

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 use -1 instead of throwing?

Throwing creates exception-handling overhead and tangles control flow. -1 is a clean in-band signal because heights are always non-negative.

Is 'balanced' the same as 'AVL-balanced'?

Same definition: every node's subtrees differ in height by at most 1. AVL trees enforce this via rotations on insert/delete.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →