Skip to main content

13. Balanced Binary Tree

easyAsked at Indeed

Determine whether a binary tree is height-balanced — mirrors how Indeed validates hierarchical job-category trees before indexing them.

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

Problem

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is one where the left and right subtrees of every node differ in height by at most 1.

Constraints

  • 0 <= number of 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. Brute force

Recursively compute height at every node and check balance independently.

Time
O(n^2)
Space
O(n)
function height(node) {
  if (!node) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}
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. Single-pass DFS with early exit

Return -1 to signal imbalance during a single post-order traversal, avoiding redundant height recomputations.

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

Tradeoff:

Indeed-specific tips

Indeed interviewers look for the single-pass sentinel approach; mentioning that taxonomy trees at scale must be validated incrementally scores bonus points.

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

Practice these live with InterviewChamp.AI →