Skip to main content

13. Balanced Binary Tree

easyAsked at Lyft

Determine if a binary tree is height-balanced.

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

  • Number of nodes in range [0, 5000]
  • -10^4 <= node value <= 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 checks

Compute height at every node and check the difference everywhere.

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

Tradeoff:

2. Bottom-up height with sentinel

Return height when balanced, -1 when unbalanced; short-circuit upward propagation.

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:

Lyft-specific tips

Lyft pushes you toward the bottom-up sentinel; they say it mirrors how they early-exit invalid quadtree builds during city-region partitioning.

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

Practice these live with InterviewChamp.AI →