#131

Balanced Binary Tree

easy

treedepth-first-searchbinary-tree

Given the root of a binary tree, return true if it is height-balanced.

A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by at most one. The check is local at every node, not just at the root.

The tree is given as a level-order array where null marks a missing child: [3, 9, 20, null, null, 15, 7] is root 3 with children 9 and 20, and 20 has children 15 and 7.

Example

Input: root = [3,9,20,null,null,15,7]9315207

Output: true

Every node's subtree heights differ by at most 1.

Constraints

The number of nodes in the tree is in the range [0, 5000].
-10^4 <= Node.val <= 10^4

Intuition

A tree is height-balanced when every node's two subtrees differ in height by at most one. The literal reading of that definition is a two-function solution: a height helper, and an isBalanced that, at every node, computes both subtree heights and checks the difference.

function isBalanced(root) {
  if (!root) return true;
  // Height of a subtree: longest path down, in edges + 1.
  const height = (node) => node ? 1 + Math.max(height(node.left), height(node.right)) : 0;
  // This node balanced?
  const diff = Math.abs(height(root.left) - height(root.right));
  // ...and both subtrees balanced, recursively.
  return diff <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

Brute force — recompute every subtree's height from scratch at each node: O(n²).

This is O(n²) — far more work than necessary. Can we do better?

The waste is that height is called over and over: checking the root computes the whole tree's heights, then checking each child recomputes its subtree's heights, and so on — every node's height is recomputed once per ancestor. But a node only needs its children's heights, and those are available the moment the children return.

The key observation: compute height bottom-up, and let it double as the balance check. Have the height function return a sentinel — -1 — the instant it discovers an imbalance, and propagate that sentinel up so the whole tree fails fast. One post-order pass, each node visited once.

Walking it through a tree whose left side runs deep while its right child is a lone leaf:

height returned bottom-up; the moment |left − right| > 1, return the −1 sentinel

height↓

h=1

leaf 5 → height 1

Post-order dives to the deepest node first. Leaf 5 has no children, so it returns height 1.

5h=1

4h=2

height↓

h=3

4h=1

node 3: |2 − 1| ≤ 1 ✓ → height 3

Node 4 (left) returns 2, node 4 (right) returns 1 — balanced. Node 3 takes 1 + max(2,1) = height 3.

3h=3

height↓

−1

node 2: |3 − 0| = 3 > 1 ✗ → return −1

The left 2 has a height-3 child and an empty (height-0) side: difference 3. Imbalance found — return the −1 sentinel.

2−1

height↓

−1

−1 seen → short-circuit, return −1

−1 bubbles straight to the root; the answer is false and the right subtree's height is never computed.

In the stored solution the value -1 is not a height — it's the "already unbalanced" flag. Any real height is >= 0, so -1 is unambiguous.
Because the check rides on the height computation, the answer is found in a single traversal rather than the brute force's repeated re-descents.

Optimization

Bottom-up height with early exit

A top-down check recomputes heights repeatedly (O(n²)). Instead, compute each subtree's height once, bottom-up, and let a sentinel of -1 mean "this subtree is already unbalanced". A node returns its own height when both children are balanced and within one of each other, otherwise it propagates -1 so the whole tree fails.

O(n) time (each node visited once), O(h) recursion space.

function isBalanced(root) {
  // Returns the subtree height, or -1 the moment an imbalance is found.
  const height = (node) => {
    if (!node) return 0;
    const left = height(node.left);
    if (left === -1) return -1;            // left subtree already unbalanced
    const right = height(node.right);
    if (right === -1) return -1;           // right subtree already unbalanced
    if (Math.abs(left - right) > 1) return -1; // imbalance at this node
    return Math.max(left, right) + 1;      // this node's height
  };
  return height(root) !== -1;
}

Complexity analysis

Time complexity: O(n). Here's why:

The bottom-up height function visits each node once and does O(1) work per node.
The -1 sentinel makes it short-circuit, so it never does more than one pass.

That's O(n), down from the brute force's O(n²) of recomputing heights at every ancestor.

Space complexity: O(h). Here's why:

Only the recursion stack, as deep as the tree height h.

O(log n) balanced, O(n) for a degenerate tree. No auxiliary structure is built.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = []null	true	Empty tree is vacuously balanced.
root = [7]7	true	Single node — both subtrees are height 0.
root = [8,4,12,2,6,10,14]2468101214	true	A perfect tree is balanced everywhere.
root = [9,5,13,3]35913	true	Left subtree height 2, right height 1: differ by exactly 1, still balanced.
root = [5,6,null,7,null,8]8765	false	A left-leaning chain of depth 3 is unbalanced at the root (2 vs 0).

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor