Skip to main content

13. Balanced Binary Tree

easyAsked at Instacart

Check if a binary tree is height-balanced — Instacart screens recursion-with-bailout fluency before harder routing-tree balance checks.

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

Problem

Given a binary tree, determine if it is height-balanced — that is, for every node, the depth difference between its left and right subtrees is at most 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. Top-down depth check

Compute depth at every node and compare children.

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

Tradeoff:

2. Bottom-up with sentinel

Return -1 from a recursive helper as soon as imbalance is found.

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:

Instacart-specific tips

Instacart wants the single-pass version — they'll ask how this would scale if applied to a delivery-zone hierarchy of 10M nodes.

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

Practice these live with InterviewChamp.AI →