Skip to main content

13. Balanced Binary Tree

easyAsked at Dropbox

Decide whether a binary tree is height-balanced; Dropbox uses it to probe single-pass DFS technique applicable to validating sync-tree invariants.

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

Problem

Given the root of a binary tree, determine if it is height-balanced (every node's two subtrees differ in height by at most 1).

Constraints

  • 0 <= nodes <= 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. Naive recompute heights

For each node, recompute left and right heights and compare. O(n^2) worst case.

Time
O(n^2)
Space
O(h)
const h=n=>!n?0:1+Math.max(h(n.left),h(n.right));
const ok=n=>!n||(Math.abs(h(n.left)-h(n.right))<=1 && ok(n.left)&&ok(n.right));
return ok(root);

Tradeoff:

2. Single-pass DFS with sentinel

Return -1 on imbalance, height otherwise. Bubbles up early on first violation.

Time
O(n)
Space
O(h)
function isBalanced(root) {
  const 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:

Dropbox-specific tips

Dropbox interviewers grade on whether you collapse height + balance into one pass — the naive O(n^2) is a red flag at L4+ phone screens.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →