Skip to main content

14. Balanced Binary Tree

easyAsked at Datadog

Determine if a binary tree is height-balanced. Datadog asks this to test the post-order single-pass trick — return both balance status and height up the stack, avoiding O(n^2) recomputation.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog backend onsite, often paired with maxDepth.
  • LeetCode Discuss (2025-09)— Datadog tagged.

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. Top-down depth calls (naive)

At each node, compute depth(left), depth(right), check diff <= 1, recurse.

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

Tradeoff: Recomputes depth for every node; n^2 in the worst case. Datadog will fail this for not caching.

2. Post-order single pass (optimal)

Recurse once. Each call returns the subtree's height — or -1 if unbalanced. Propagate -1 up to short-circuit.

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

Tradeoff: Single pass; -1 sentinel signals 'subtree unbalanced.' This is the Datadog-canonical pattern: return one value, encode a side condition with a sentinel.

Datadog-specific tips

Datadog interviewers grade on whether you avoid the O(n^2) trap. The -1 sentinel pattern (or a `[height, balanced]` tuple) is the expected solution. Articulate why caching height during the same traversal is the right call before coding.

Common mistakes

  • Forgetting to short-circuit when a subtree returns -1 — falls back to O(n^2).
  • Using a tuple/array return type in JS and forgetting to destructure — wastes time on noise.
  • Returning depth instead of unbalanced-or-depth — conflates two signals.

Follow-up questions

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

  • Convert Sorted Array to BST (LC 108) — construct a balanced tree.
  • AVL rotations — maintain balance on insert.
  • Datadog-style: 'Is this on-disk tree-index balanced?' — same algo over a streaming reader.

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 instead of throwing an exception?

Exceptions for control flow are slow in V8. -1 is a clean sentinel because heights are non-negative.

What's 'balanced' exactly?

Every node's left and right subtree heights differ by at most 1. This is the AVL definition, stricter than 'not skewed.'

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →