Skip to main content

13. Balanced Binary Tree

easyAsked at Snowflake

Decide whether a binary tree is height-balanced (every subtree's left/right heights differ by at most 1). Snowflake asks this to test whether you can fuse the 'check' and 'measure' passes into one — the same fusing the query planner does to avoid re-scanning data.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake storage team uses this in onsite to discuss B-tree balancing.
  • LeetCode Discuss (2025-11)— Reported at Snowflake new-grad screens.

Problem

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

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. Compute height at each node

For each node, compute left and right heights; if they differ by > 1, return false. Recurse.

Time
O(n^2) worst case (skewed tree)
Space
O(h)
function isBalanced(root) {
  function height(n) {
    if (!n) return 0;
    return 1 + Math.max(height(n.left), height(n.right));
  }
  if (!root) return true;
  if (Math.abs(height(root.left) - height(root.right)) > 1) return false;
  return isBalanced(root.left) && isBalanced(root.right);
}

Tradeoff: Recomputes height at every node. Quadratic. Mention as the obvious-but-slow baseline.

2. Bottom-up single pass (optimal)

Helper returns height when balanced, -1 when not. Propagate -1 up the tree as a sentinel.

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

Tradeoff: Single pass, fused. The same fusion a query planner does to combine filter + aggregate into one scan.

Snowflake-specific tips

Snowflake interviewers grade this on whether you spot the redundant work in the naive solution and fuse into a single pass. Bonus signal: connect to query-plan operator fusion — Snowflake's planner combines filter + map + aggregate into one fused pipeline to avoid materializing intermediate batches.

Common mistakes

  • Using a global flag instead of a sentinel return — works but is harder to reason about.
  • Returning -1 from null nodes — that's wrong, null is balanced with height 0.
  • Forgetting to short-circuit when left side returns -1, doing extra work on the right.

Follow-up questions

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

  • Self-balancing BST (AVL or Red-Black) — when would Snowflake actually use one?
  • Diameter of binary tree (LC 543) — same single-pass pattern.
  • Maximum path sum (LC 124) — same dual-return idea.

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 use -1 as a sentinel?

Heights are non-negative. -1 cleanly signals 'subtree is unbalanced' without needing a separate boolean. Some prefer returning a [height, balanced] tuple — equivalent.

Why does Snowflake fuse operators?

Each unfused operator materializes a batch, paying allocation and cache-miss cost. Fusing means one pass over the data with all transformations inlined, which keeps the working set in CPU cache.

More Snowflake coding interview questions

See all Snowflake problems →

Companies that also ask Balanced Binary Tree