Skip to main content

13. Balanced Binary Tree

easyAsked at Salesforce

Determine if a binary tree is height-balanced (every node's left and right subtree differ in height by at most 1). Salesforce uses this to test the bottom-up pattern that avoids the O(n^2) trap.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce Apex compiler team uses tree-balance checks to validate hierarchy assertions.
  • LeetCode Discuss (2025-09)— Asked specifically to test bottom-up vs top-down recursion.

Problem

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

Constraints

  • The number of nodes in the tree is in the range [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

Example 3

Input
root = []
Output
true

Approaches

1. Top-down: compute height per node

For each node, recompute height of left and right and check the difference. Recurse into children.

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

Tradeoff: Quadratic because height is recomputed at every node. Salesforce flags this in mid-loop.

2. Bottom-up: height returns -1 on imbalance

Compute height once, returning -1 as a sentinel if any subtree is unbalanced. Short-circuit at every level.

Time
O(n)
Space
O(h)
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: Single O(n) pass. The -1 sentinel piggybacks 'unbalanced' onto the height return value, avoiding a second pass.

Salesforce-specific tips

Salesforce specifically asks this to test whether you spot the O(n^2) trap in the naive solution. Bonus signal: articulate WHY the bottom-up version is O(n) (each subtree's height is computed once, not once per ancestor). They like the sentinel-value pattern because it's heavily used in their query optimizer.

Common mistakes

  • Using the top-down version and not realizing it's O(n^2) on skewed trees.
  • Returning the height instead of a boolean from the wrapper — breaks the contract.
  • Forgetting to short-circuit when left or right returns -1 — wastes work and may continue with bogus heights.

Follow-up questions

An interviewer at Salesforce may pivot to one of these next:

  • Convert Sorted Array to BST (LC 108) — produces a balanced BST.
  • Self-balancing tree (AVL, Red-Black) — rotation logic.
  • Detect 'almost balanced' — at most k unbalanced subtrees allowed.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the top-down version O(n^2)?

Because height() is called for every node, and each call traverses its subtree. On a balanced tree of depth log(n), the total work is O(n log n); on a skewed tree, it's O(n^2).

Why use -1 as a sentinel instead of throwing?

Throwing is fine but slower (exception unwinding). -1 is impossible as a real height (which is always >= 0), so it's a safe sentinel.

Practice these live with InterviewChamp.AI

Drill Balanced Binary Tree and other Salesforce interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →