Skip to main content

13. Balanced Binary Tree

easyAsked at Asana

Determine if a binary tree is height-balanced. Asana asks this to test whether you spot the O(n) early-exit pattern — they care because the same trick speeds up their dependency-imbalance detector.

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

Source citations

Public interview reports confirming this problem appears in Asana loops.

  • Glassdoor (2026-Q1)— Asana tree-recursion warmup.

Problem

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than 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: compute height twice

At each node, recompute left and right heights, check |diff| <= 1, recurse on children.

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

Tradeoff: Recomputes height O(n) times — O(n^2). Asana flags this as a missed optimization.

2. Bottom-up with early exit sentinel

Return height when balanced, -1 when unbalanced. Any -1 propagates up.

Time
O(n)
Space
O(h)
function isBalanced(root) {
  const 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: Single pass. The -1 sentinel collapses height-and-balance into one return value — the Asana favorite trick.

Asana-specific tips

At Asana, the -1-as-sentinel pattern is the bonus signal. State it explicitly: 'I'll fold the height and the balanced flag into one return value to avoid recomputing height at every level.' That conciseness in framing is exactly what they grade.

Common mistakes

  • Forgetting to propagate -1 up — checking balance only at the root level.
  • Recomputing height inside the recursion — O(n^2).
  • Using a boolean and a height separately, doubling the return type.

Follow-up questions

An interviewer at Asana may pivot to one of these next:

  • Construct a balanced BST from a sorted array (LC 108).
  • Self-balancing trees — what makes AVL different?
  • What if balance is defined as |diff| <= k for arbitrary k?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is -1 safe as a sentinel?

Heights are non-negative integers, so -1 is unreachable as a real height. This makes 'returned -1' an unambiguous signal.

Could you use exceptions instead?

Yes, but exception-based control flow has a much higher constant. The sentinel is the idiomatic functional pattern.

Practice these live with InterviewChamp.AI

Drill Balanced Binary Tree and other Asana interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →