Skip to main content

13. Balanced Binary Tree

easyAsked at Glassdoor

Return whether a binary tree is height-balanced — Glassdoor uses this to test whether you can fold height + balance into one O(n) post-order traversal.

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

Problem

Given a binary tree, determine if it is height-balanced. A balanced tree has the depth of its left and right subtrees differ by no more than one at every node.

Constraints

  • The 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 height

At each node, compute height of both sides and compare.

Time
O(n^2)
Space
O(h)
function isBalanced(root) {
  if (!root) return true;
  return Math.abs(height(root.left) - height(root.right)) <= 1
    && isBalanced(root.left) && isBalanced(root.right);
}

Tradeoff:

2. Bottom-up height (single pass)

Return -1 sentinel from any subtree that is unbalanced; short-circuits the work.

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:

Glassdoor-specific tips

Glassdoor grades for the single-pass insight — they're a data-aggregation shop and want you to fold work into the same traversal whenever possible.

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

Practice these live with InterviewChamp.AI →