Tree problem patterns

Tree questions look varied and reduce to a few skeletons. Recognising which one you need is most of the work.

1. Bottom-up: children answer first

Compute something for each subtree and combine. Use when the parent's answer depends on the children's.

// Balanced check in one pass: -1 means "already unbalanced below here".
function heightOrFail(node) {
  if (!node) return 0;

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

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

  if (Math.abs(left - right) > 1) return -1;
  return 1 + Math.max(left, right);
}

O(n), against O(n log n) for the naive version that recomputes height at every node. The sentinel return value carrying two meanings is a pattern worth stealing.

2. Top-down: pass context to children

Use when a node's answer depends on where it sits — path sums, valid ranges, depth.

function pathsToLeaves(node, path = [], out = []) {
  if (!node) return out;

  path.push(node.value);

  if (!node.left && !node.right) out.push(path.join('->'));
  else {
    pathsToLeaves(node.left, path, out);
    pathsToLeaves(node.right, path, out);
  }

  path.pop();          // backtrack — the same discipline as chapter 6
  return out;
}

3. Global accumulator with a local return

Some problems have an answer that does not pass cleanly up the recursion. Return one thing, record another.

// Diameter: the longest path may not go through the root.
function diameter(root) {
  let best = 0;

  const depth = (node) => {
    if (!node) return 0;

    const left = depth(node.left);
    const right = depth(node.right);

    best = Math.max(best, left + right);      // record: path through this node
    return 1 + Math.max(left, right);         // return: depth, for the parent
  };

  depth(root);
  return best;
}

The same shape solves "maximum path sum", where you also clamp negative contributions to zero.

Lowest common ancestor

Worth knowing outright. In a plain binary tree, return the node where the two targets first appear in different subtrees:

function lca(node, a, b) {
  if (!node || node =<mark> a || node </mark>= b) return node;

  const left = lca(node.left, a, b);
  const right = lca(node.right, a, b);

  return left && right ? node : (left ?? right);
}

In a BST it is easier: walk down while both targets are on the same side, and the first node that splits them is the answer — O(h) with no recursion needed.