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 Sam K., 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.

More Workday coding interview questions

See all Workday problems →

Companies that also ask Balanced Binary Tree