Skip to main content

14. Balanced Binary Tree

easyAsked at Expedia

Determine 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. 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

  • Number of nodes in [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. Repeated depth calls

For each node compute both subtree depths.

Time
O(n^2)
Space
O(h)
function depth(n){if(!n)return 0;return 1+Math.max(depth(n.left),depth(n.right));}
function check(n){if(!n)return true;
  if(Math.abs(depth(n.left)-depth(n.right))>1)return false;
  return check(n.left)&&check(n.right);}

Tradeoff:

2. Post-order height with early exit

Return -1 to signal unbalanced subtree. Expedia uses this single-pass approach when validating balanced bundle trees.

Time
O(n)
Space
O(h)
function isBalanced(root) {
  function h(n) {
    if (!n) return 0;
    const l = h(n.left);
    if (l === -1) return -1;
    const r = h(n.right);
    if (r === -1 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  }
  return h(root) !== -1;
}

Tradeoff:

Expedia-specific tips

Expedia interviewers grade the O(n) single-pass solution explicitly; the naive O(n^2) signals you missed the early-exit trick.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Expedia coding interview questions

See all Expedia problems →

Companies that also ask Balanced Binary Tree