Skip to main content

13. Balanced Binary Tree

easyAsked at Quora

Check whether 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 — every node's left and right subtrees differ in height by at most one.

Constraints

  • 0 <= 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. Depth at every node

Compute height twice per node — O(n^2).

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

Tradeoff:

2. Single post-order with sentinel

Return -1 from a recursive height once imbalance is detected.

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 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  };
  return check(root) !== -1;
}

Tradeoff:

Quora-specific tips

Quora reaches for early-termination tree walks because their topic-tree balancer must reject lopsided merges without paying for a full second pass.

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

Practice these live with InterviewChamp.AI →