Balanced Binary Tree

Examples

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

Checking every node, the left and right subtree heights never differ by more than 1.

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

The subtree rooted at the first '2' has a left height of 2 and a right height of 0 - a difference of 2, which breaks the balance rule.

Input: root = []
Output: true

An empty tree is trivially balanced - there are no nodes to violate the rule.

Constraints

• The number of nodes in the tree is in the range [0, 5000].

• -10^4 <= Node.val <= 10^4

Approach

A naive approach checks the balance condition at the root, then separately recomputes the height of every subtree to check balance again inside them - that duplicated height work makes it slow.

The efficient approach folds both jobs into one recursive traversal: a helper function computes a subtree's height, but if it ever finds an imbalance in a child subtree, it immediately reports that upward using a sentinel value (like -1) instead of a real height. Any parent call that sees that sentinel knows to also report "unbalanced" without doing any more work, so a single bottom-up pass is enough.

Solutions

Brute Force — Height Recomputed at Every Node

At each node, compute left and right subtree heights (each its own recursive call) and check they differ by at most 1, then recurse into both children to check the same condition there.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function height(node) {
  if (node === null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

function isBalanced(root) {
  if (root === null) return true;

  const diff = Math.abs(height(root.left) - height(root.right));

  if (diff > 1) return false;

  return isBalanced(root.left) && isBalanced(root.right);
}

Time: O(n²) — height() recomputes overlapping subtree heights at every node · Space: O(h) — recursion stack depth

Optimal — Height + Balance Check in One Pass

Write a helper that returns a subtree's height, but returns -1 the instant it detects an imbalance anywhere below. Any call that receives -1 from a child immediately passes -1 up too, so the whole tree only needs one pass.

function isBalanced(root) {
  function height(node) {
    if (node === null) return 0;

    const leftHeight = height(node.left);
    if (leftHeight === -1) return -1;

    const rightHeight = height(node.right);
    if (rightHeight === -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) return -1;

    return 1 + Math.max(leftHeight, rightHeight);
  }

  return height(root) !== -1;
}

Time: O(n) · Space: O(h) — recursion stack depth, where h is the tree's height (O(n) worst case)