Skip to main content

14. Balanced Binary Tree

easyAsked at Databricks

Determine if a binary tree is height-balanced. Databricks asks this to test the post-order pattern where you return information up the tree to avoid recomputing heights at every node.

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

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • LeetCode Discuss (2025-11)— Databricks SDE-II onsite warm-up.
  • Glassdoor (2026-Q1)— Used to test 'avoid O(n^2) recomputation' awareness.

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

Approaches

1. Top-down height check at every node

At each node, compute heights of both subtrees and compare.

Time
O(n^2) worst case
Space
O(h)
function isBalanced(root) {
  function height(n) { return !n ? 0 : 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 — O(n^2) on skewed trees. Mention only to motivate the better version.

2. Bottom-up: return height OR -1 sentinel for unbalanced

Post-order recursion. Return -1 if any subtree is unbalanced; otherwise return the height. Short-circuit on -1.

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 post-order pass. The -1 sentinel piggybacks the boolean answer onto the height return — clean trick.

Databricks-specific tips

Databricks grades the post-order single-pass pattern specifically — the bonus signal is recognizing the O(n^2) trap of the naive solution and articulating that the bottom-up approach is the same pattern they use in cost-aware plan validation (return data up the tree, fail fast). Volunteer the -1 sentinel technique; it's the cleanest way to combine an int return with a boolean signal.

Common mistakes

  • Computing height at each node from scratch — the O(n^2) trap.
  • Using a separate boolean parameter instead of the sentinel — works but is uglier.
  • Forgetting that empty subtrees have height 0, not -1.

Follow-up questions

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

  • Return BOTH the height and the balanced flag using a tuple — slightly cleaner but more memory.
  • Convert sorted array to balanced BST (LC 108).
  • How does Catalyst guarantee its plan trees stay 'balanced enough' for stack-safe traversal?

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 bottom-up vs top-down?

Top-down computes height at each node independently — same subtree is measured many times. Bottom-up measures each subtree exactly once and propagates upward.

Why -1 as a sentinel?

Heights are non-negative, so -1 is a safe out-of-band signal. Saves a boolean parameter or a tuple return.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →