Skip to main content

13. Balanced Binary Tree

easyAsked at GoDaddy

Check whether a binary tree is height-balanced.

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

Problem

Given a binary tree, determine if it is height-balanced — a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

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. Top down depth recompute

For each node, compute left/right depth and check diff.

Time
O(n^2)
Space
O(h)
// recompute depth at each node, costly

Tradeoff:

2. Bottom up with early exit

Return -1 from recursion on first imbalance; otherwise return height.

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

Tradeoff:

GoDaddy-specific tips

GoDaddy uses this to test whether candidates can quickly flag a misbalanced load tree where one hosting region is doing too much DNS lookup work.

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

Practice these live with InterviewChamp.AI →