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

More Datadog coding interview questions

See all Datadog problems →

Companies that also ask Balanced Binary Tree