Balanced Binary Tree

EasyTreesTreeDFSBinary Tree

Problem

Given the root of a binary tree, determine whether it is height-balanced: for every node, its left and right subtree heights must differ by no more than one. The tree is unbalanced if even a single node violates this, no matter how deep that node sits.

Example. A root 3 with left child 9 and right child 20, where 20 has children 15 and 7, is balanced, since every node's two sides differ by at most one. If 9 also had a left child with its own left child, the left side under 3 would be two levels deeper than the right, making it unbalanced.

Key idea

A direct approach computes the left and right subtree heights at every node from scratch and recurses, but recomputing a subtree's height every time an ancestor checks it wastes work, giving O(n squared) in the worst case on a skewed tree.

The fix is to compute height and check balance in the same bottom-up pass, so each subtree's height is calculated once. Recurse into both children to get their heights. If either reports unbalanced, using a sentinel such as negative one, propagate that failure up without further work. Otherwise compare the two heights: if they differ by more than one, return the sentinel; if not, return one plus the larger height for the parent to use. The final answer is simply whether the root's result was a failure.

Solution

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

function isBalanced(root: TreeNode | null): boolean {
  // sentinel that signals an already-unbalanced subtree
  const UNBALANCED = -1;

  function checkHeight(node: TreeNode | null): number {
    if (node === null) {
      return 0;
    }

    const leftHeight = checkHeight(node.left);
    if (leftHeight === UNBALANCED) {
      // propagate the failure up instead of checking the right side
      return UNBALANCED;
    }

    const rightHeight = checkHeight(node.right);
    if (rightHeight === UNBALANCED) {
      return UNBALANCED;
    }

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

    // heights are fine here, so report height for the parent's own check
    return 1 + Math.max(leftHeight, rightHeight);
  }

  return checkHeight(root) !== UNBALANCED;
}

Complexity

  • Time: O(n). Each node's height is computed exactly once, and failures short-circuit further comparisons.
  • Space: O(h). The recursion stack depth equals the tree's height.

Watch out for

  • Recomputing height separately at each node, rather than merging it with the balance check, silently degrades this to O(n squared), a common trap.
  • An empty subtree has height 0 and is trivially balanced; do not treat null as an error.
  • The imbalance check must run at every node, not only comparing the root's two children.

Pattern

This is post-order aggregation combined with early termination: once a subtree is known unbalanced, there is no need to keep measuring the rest of the tree. The same shape, computing a value while propagating a failure signal upward, shows up whenever a global property depends on a local check at every node.

Related questions