Skip to main content

13. Balanced Binary Tree

easyAsked at Booking

Decide if a binary tree is height-balanced — Booking screens this to gauge whether you can keep destination index trees from skewing.

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

Problem

Given a binary tree, determine if it is height-balanced — for every node, the depth of left and right subtrees differs by at most 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. Top-down height calc

At each node, compute left and right heights independently — O(n log n) at best.

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

Tradeoff:

2. Bottom-up with sentinel

Return -1 to signal unbalanced; otherwise return the actual height in one pass.

Time
O(n)
Space
O(h)
function isBalanced(root) {
  const check = (n) => {
    if (!n) return 0;
    const l = check(n.left); if (l === -1) return -1;
    const r = check(n.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:

Booking-specific tips

Booking will probe constant-time short-circuit on imbalance — link it to early-rejecting a malformed destination index update.

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

Practice these live with InterviewChamp.AI →