Skip to main content

14. Balanced Binary Tree

easyAsked at Workday

Determine if a binary tree is height-balanced. Workday uses this to catch sloppy 'recompute depth at every node' candidates — at org-chart scale, that's O(n^2).

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 phone — tree warmup.

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. Naive: depth at every node

At each node, compute left-depth and right-depth recursively; recurse to children.

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

Tradeoff: Recomputes depth from scratch at each node — O(n^2) on skewed trees.

2. Single-pass DFS returning (depth or -1)

Recurse once, returning depth on balanced or sentinel -1 on imbalanced. Short-circuit on -1.

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

Tradeoff: Each node visited once. The -1 sentinel doubles as 'imbalance found, stop'.

Workday-specific tips

Workday grades the time complexity — getting O(n^2) is a hard signal that you don't see the wasted work. State 'I'll do one pass with an imbalance sentinel' before coding to lock in the better approach.

Common mistakes

  • Doing the naive O(n^2) — even if it works, it's the wrong answer at scale.
  • Forgetting to short-circuit on the sentinel — burns time on already-unbalanced trees.
  • Returning false when l === -1 instead of propagating — works but mixes concerns.

Follow-up questions

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

  • Convert sorted array to balanced BST (LC 108).
  • Self-balancing trees — AVL, red-black.
  • What if the tree is a DAG?

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

All valid depths are >= 0. -1 is unambiguous and easy to check.

Could I throw an exception to short-circuit instead?

Yes, but exceptions are expensive in JS and signal panic. The sentinel is idiomatic.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →