#437 - Path Sum III

MediumBinary Tree - DFS

Given the root of a binary tree and an integer targetSum, return the number of paths where the values along the path sum to targetSum. The path does not need to start at the root or end at a leaf, but it must go downwards (from parent to child).

Input	Output
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8	3
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22	3

Solution Space

Try it

/**
 * Counts paths summing to targetSum using prefix-sum technique.
 *
 * @param root      Root of the binary tree
 * @param targetSum Target path sum
 * @returns         Number of valid downward paths
 */
export function pathSum(root: TreeNode | null, targetSum: number): number {
  // Map from prefix sum → number of times it has occurred on the current root-to-node path
  const prefixMap = new Map<number, number>();
  prefixMap.set(0, 1); // empty prefix

  return dfs(root, 0, targetSum, prefixMap);
}

function dfs(
  node: TreeNode | null,
  currentSum: number,
  target: number,
  prefixMap: Map<number, number>,
): number {
  if (!node) return 0;

  currentSum += node.val;

  // How many prefixes give us a sub-path summing to target
  let count = prefixMap.get(currentSum - target) ?? 0;

  // Record this prefix sum
  prefixMap.set(currentSum, (prefixMap.get(currentSum) ?? 0) + 1);

  count += dfs(node.left, currentSum, target, prefixMap);
  count += dfs(node.right, currentSum, target, prefixMap);

  // Backtrack: remove this prefix sum before returning to parent
  prefixMap.set(currentSum, prefixMap.get(currentSum)! - 1);

  return count;
}

Approach: DFS + prefix sum map – at each node, `currentSum - target` tells us the prefix sum we need to have seen earlier; the map counts how many such prefixes exist on the current path.

Time: O(n) – each node visited once with O(1) map operations.

Space: O(n) – prefix map can hold up to n entries, plus O(h) recursion stack.

Alternative approaches:

Approach	Idea	Time	Space
Brute force DFS from every node	For each node, start a separate DFS counting paths summing to target	O(n²) worst case	O(h)

Why the prefix-sum method is preferred: reduces O(n²) to O(n) by reusing accumulated prefix sums, analogous to the subarray-sum technique on arrays.

#236 Lowest Common Ancestor of a Binary Tree

#872 Leaf-Similar Trees