Skip to main content

13. Balanced Binary Tree

easyAsked at Spotify

Check if a binary tree is height balanced.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a binary tree, determine if it is height-balanced — for every node, the heights of left and right subtrees differ 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. Recompute height per node

For each node compute height of left and right and compare

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

Tradeoff:

2. Single-pass DFS with early exit

Return height or -1 if imbalanced. Propagates failure upward in one O(n) pass.

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

Spotify-specific tips

Spotify graders care about avoiding the quadratic recompute trap — flag it explicitly and pivot to the single-pass sentinel technique.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Spotify coding interview questions

See all Spotify problems →

Companies that also ask Balanced Binary Tree