Skip to main content

13. Balanced Binary Tree

easyAsked at Plaid

Determine if a binary tree is height-balanced. Plaid asks this because their internal category trees must stay balanced for predictable lookup latency — and detecting imbalance is the prerequisite for triggering a rebuild.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid backend screen — framed around category-tree balance.
  • LeetCode Discuss (2026)— Reported as Plaid intro.

Problem

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

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 for every node

At each node, recompute heights of both subtrees and check the difference.

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

Tradeoff: Re-walks the tree for every node. O(n^2) worst case on a skewed tree.

2. Single DFS returning height OR -1 for imbalance

Bottom-up: return height of subtree, or sentinel -1 if any subtree is imbalanced. Propagate -1 up.

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 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  }
  return dfs(root) !== -1;
}

Tradeoff: Single pass. The -1 sentinel is the clean way to encode 'I found an imbalance, short-circuit.' Plaid loves this pattern because it's what they use to bubble up validation errors in ETL.

Plaid-specific tips

Plaid grades this on whether you avoid the O(n^2) trap by carrying height up as a return value. Bonus signal: name the -1 sentinel pattern as 'short-circuit return' and mention how it generalizes to ETL validation pipelines where a single bad row should abort the whole pass.

Common mistakes

  • Calling height() recursively from isBalanced() — quadratic.
  • Returning a {height, balanced} object — works but the sentinel is cleaner.
  • Forgetting to short-circuit when the left subtree is already imbalanced.

Follow-up questions

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

  • Return the deepest imbalanced node, not just a boolean.
  • Rebalance the tree (full AVL rotation) — harder.
  • Same problem on an N-ary category tree.

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 a sentinel?

Heights are always >= 0, so -1 is unambiguous and avoids an extra object allocation per call.

Why is the naive version O(n^2)?

For a skewed tree, height() at the root walks all n nodes, then again for each of its n-1 children, etc.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →