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 Alex Chen, 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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →