# Balanced Binary Tree

> How to solve Balanced Binary Tree: check whether every nodes two subtree heights differ by at most one in a single bottom-up pass.

- Difficulty: Easy
- Category: Trees
- Topics: Tree, DFS, Binary Tree
- Published 2026-08-21

## 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

```typescript
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.

---

Canonical URL: https://www.marauderbot.com/questions/balanced-binary-tree
