Given a binary tree and a distance, count how many pairs of leaf nodes have a shortest-path length of at most distance.

Engineering takeaway. The shortest path between two leaves always passes through their lowest common ancestor (LCA). Once you internalize that, this problem is either "compare root-to-leaf paths" (simple, O(d²) with d leaves) or "pass leaf-distance counts up the tree" (one DFS, O(n·distance)). Choosing the second is the kind of optimization that separates a working solution from a fast one.

Intuition

For two leaves, the shortest path is leafA → LCA → leafB. So a pair is "good" when:

depth(A) + depth(B) - 2 * depth(LCA) <= distance

There are two clean ways to measure this.

Approach 1 — compare root-to-leaf paths (simple)

Record the path from the root to every leaf as a string of L/R moves. Two leaves share a common prefix down to their LCA; strip that prefix and the remaining length of each side is the distance.

function countPairs(root: TreeNode | null, distance: number): number {
  let result = 0;
  const leaves: string[] = [];
 
  const collect = (node: TreeNode | null, path = ""): void => {
    if (node.left === null && node.right === null) {
      leaves.push(path);
      return;
    }
    if (node.left !== null) collect(node.left, path + "L");
    if (node.right !== null) collect(node.right, path + "R");
  };
 
  collect(root);
 
  for (let i = 0; i < leaves.length; i++) {
    for (let j = i + 1; j < leaves.length; j++) {
      let a = leaves[i];
      let b = leaves[j];
 
      while (a.length > 0 && b.length > 0 && a[0] === b[0]) {
        a = a.slice(1);
        b = b.slice(1);
      }
 
      if (a.length + b.length <= distance) result++;
    }
  }
 
  return result;
}

This is easy to reason about, but for d leaves it's O(d²) path-strips.

Approach 2 — pass leaf-distance counts up the tree (faster)

Here's the nicer idea: each node returns an array where arr[k] = the number of leaves in its subtree exactly k edges below it. A leaf returns [1] (distance 0, itself).

At every node we:

  1. Count pairs formed by one leaf from the left subtree and one from the right, summing the distances (leftDist + 1) + (rightDist + 1).
  2. Merge the two child arrays, bumping every distance by 1, and return it.
function countPairs(root: TreeNode | null, distance: number): number {
  let result = 0;
 
  const dfs = (node: TreeNode | null): number[] => {
    if (node === null) return [];
 
    if (node.left === null && node.right === null) {
      return [1]; // a leaf: 1 leaf at distance 0
    }
 
    const left = dfs(node.left);
    const right = dfs(node.right);
 
    // Count good pairs across the two subtrees
    for (let i = 0; i < left.length; i++) {
      for (let j = 0; j < right.length; j++) {
        if (i + j + 2 <= distance) result++;
      }
    }
 
    // Merge distances, shifted up by 1
    const merged = new Array(Math.max(left.length, right.length) + 1).fill(0);
    for (let i = 0; i < left.length; i++) merged[i + 1] += left[i];
    for (let j = 0; j < right.length; j++) merged[j + 1] += right[j];
 
    return merged;
  };
 
  dfs(root);
  return result;
}

Because distance is small (≤ 10), the inner loops are cheap, giving O(n · distance).

Complexity

  • Time: O(n · distance) — each node does work proportional to distance.
  • Space: O(n) for the recursion stack and the per-node arrays.

The lesson

The "compare two root-to-leaf paths" framing is a great first intuition — it makes the LCA structure obvious. The upgrade is to fold that comparison into a single post-order traversal so each leaf's distance is computed once and reused. When a problem says "pairs in a tree within some distance," a return-a-small-array-from-each-node DFS is usually the answer.