Skip to main content

13. Balanced Binary Tree

easyAsked at Box

Verify that a binary tree is height-balanced — Box uses this when verifying rebalanced folder-shard trees after a metadata-store split.

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

Problem

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

Constraints

  • 0 <= number of 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 depth at each node

For each node compute left and right depth; expensive O(n^2).

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

Tradeoff:

2. Bottom-up DFS

Return height or -1 sentinel for unbalanced subtrees; propagates up in one pass.

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

Tradeoff:

Box-specific tips

Box wants the bottom-up sentinel pattern — they map it directly to validating rebalanced shard-routing trees after metadata-store splits.

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 Box interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →