Skip to main content

13. Balanced Binary Tree

easyAsked at Roblox

Determine if a binary tree is height-balanced.

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

Problem

Given a binary tree, determine if it is height-balanced — a tree where for every node the depth of the two subtrees differs by no more than one.

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. Per-node depth recompute

Compute depth for every node; cubic on skewed trees.

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

Tradeoff:

2. Bottom-up height with early exit

Return -1 as an unbalanced sentinel so each node is visited once.

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

Roblox-specific tips

Roblox interviewers reward the single-pass DFS because the same shape appears when measuring how unbalanced a CSG operation tree has become.

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

Practice these live with InterviewChamp.AI →