Skip to main content

13. Balanced Binary Tree

easyAsked at Ola

Determine whether 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 binary tree is height-balanced if for every node the depths of left and right subtrees differ by at most one.

Constraints

  • Number of nodes is 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. Top-down recompute

For every node compute heights of subtrees and compare.

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

Tradeoff:

2. DFS returning height or -1

Each recursive call returns subtree height or -1 if any descendant is unbalanced. Single pass.

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

Tradeoff:

Ola-specific tips

Ola will probe whether you collapse two passes into one return signal; relate it to flagging skewed subtrees in a partitioned driver-pool tree.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Ola coding interview questions

See all Ola problems →

Companies that also ask Balanced Binary Tree