Path Sum / Path Sum III: root-to-leaf path / all downward paths summing to target

• Path Sum checks if any root-to-leaf path sums to a target by subtracting each node's value and testing zero at a leaf.
• Path Sum III counts all downward paths (any start, any end) summing to the target.
• Prefix-sum HashMap maps running sums to their frequency on the current root-to-node path.
• Key insight is that a path from ancestor A to current node C sums to target when prefixSum(C) - prefixSum(A) == target.
• Backtracking decrements the map on return to prevent counts from leaking across branches.
• Time is O(n) with the map; space is O(h) for the map entries and call stack.

What is Path Sum?

Path Sum asks whether any root-to-leaf path in a binary tree has node values that sum to a given target. It is the simplest path-sum variant: recurse down subtracting each value, and at a leaf check if the remainder is zero.

package com.bank.service;

public class TransactionChainValidator {
    // Path Sum: does any root-to-leaf path sum to target?
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        targetSum -= root.val;
        if (root.left == null && root.right == null) {
            return targetSum == 0;
        }
        return hasPathSum(root.left, targetSum)
            || hasPathSum(root.right, targetSum);
    }
}

Tree:        5           Target = 22
            / \
           4    8
          /    / \
         11   13   4
        / \         \
       7   2         1

Path [5,4,11,2] sums to 22 → true

What is Path Sum III?

Path Sum III generalizes the problem: count every downward path (not necessarily starting at the root or ending at a leaf) whose values sum to the target. A downward path is any sequence of consecutive nodes from parent to child.

The naive approach starts a fresh sum from every node and explores all paths downward, running in O(n * h) time. The efficient approach uses prefix sums and a HashMap.

How does the prefix-sum HashMap work?

As you walk from the root to the current node, you maintain a running sum. A downward path ending at the current node sums to the target exactly when some ancestor had a prefix sum equal to runningSum - target. The HashMap tracks how many times each prefix sum has occurred on the current root-to-node path.

import java.util.HashMap;
import java.util.Map;

public class FraudSubChainCounter {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0L, 1);  // seed: path from root
        return dfs(root, 0L, targetSum, prefixCounts);
    }

    private int dfs(TreeNode node, long runningSum, int target,
                    Map<Long, Integer> prefixCounts) {
        if (node == null) return 0;

        runningSum += node.val;

        // Count paths ending here that sum to target
        int count = prefixCounts.getOrDefault(
            runningSum - target, 0);

        // Record current running sum
        prefixCounts.merge(runningSum, 1, Integer::sum);

        // Recurse into children
        count += dfs(node.left, runningSum, target, prefixCounts);
        count += dfs(node.right, runningSum, target, prefixCounts);

        // Backtrack: remove current running sum
        prefixCounts.merge(runningSum, -1, Integer::sum);

        return count;
    }
}

Tree:        10          Target = 8
            / \
           5   -3
          / \    \
         3   2    11
        / \   \
       3  -2   1

Paths summing to 8:
  [5, 3]  (nodes 5→3)
  [5, 2, 1]  (nodes 5→2→1)
  [-3, 11]  (nodes -3→11)
  Count = 3

Why is the backtracking step critical?

When you return from a node, you must decrement its running sum from the HashMap. Without this step, the prefix sums from one branch leak into sibling branches, inflating the count. This is the detail that separates people who understand the algorithm from people who memorized it.

// WRONG: no backtracking
prefixCounts.merge(runningSum, 1, Integer::sum);
count += dfs(node.left, runningSum, target, prefixCounts);
count += dfs(node.right, runningSum, target, prefixCounts);
// Missing: prefixCounts.merge(runningSum, -1, Integer::sum);
// Prefix sums from left branch leak into right branch!

// CORRECT: backtrack after both children
prefixCounts.merge(runningSum, 1, Integer::sum);
count += dfs(node.left, runningSum, target, prefixCounts);
count += dfs(node.right, runningSum, target, prefixCounts);
prefixCounts.merge(runningSum, -1, Integer::sum);  // cleanup

Why seed the map with zero?

Seeding prefixCounts.put(0L, 1) handles paths that start from the root. When the running sum at some node equals the target, runningSum - target == 0, and the seeded zero entry provides a count of 1, correctly counting the root-to-node path.

How do Path Sum and Path Sum III compare?

| Aspect | Path Sum | Path Sum III |
|--------|----------|-------------|
| Path constraint | Root-to-leaf only | Any downward path |
| Return type | boolean | int (count) |
| Technique | Subtract and check at leaf | Prefix-sum HashMap |
| Time | O(n) | O(n) with map, O(n*h) naive |
| Backtracking | Not needed | Critical for correctness |

What are edge cases?

• Empty tree: Path Sum returns false, Path Sum III returns 0.
• Single node equal to target: Path Sum returns true (it is a leaf), Path Sum III returns 1.
• Negative node values: both algorithms handle them correctly because subtraction and prefix sums work with negatives.
• Integer overflow: use long for the running sum because large node values can exceed int range.

// Edge case: single node
// Tree: [5], Target = 5
// Path Sum: true (leaf with val == target)
// Path Sum III: 1 (one path containing just the root)

What are common mistakes?

The first mistake is forgetting to backtrack the HashMap in Path Sum III. The second is not seeding the map with zero. The third is using int instead of long for the running sum, which overflows with large cumulative values.

// WRONG: int running sum overflows
int runningSum = 0;  // can overflow with nodes like Integer.MAX_VALUE

// CORRECT: long running sum
long runningSum = 0L;  // safe for large cumulative values

What about the naive Path Sum III approach?

The naive approach runs a Path-Sum-style check from every node, giving O(n * h) time. For each node, it starts a new sum and explores all downward paths. This is conceptually simple but too slow for large trees.

// Naive: O(n * h) approach
public int pathSumNaive(TreeNode root, int target) {
    if (root == null) return 0;
    return countFromNode(root, target)
         + pathSumNaive(root.left, target)
         + pathSumNaive(root.right, target);
}

private int countFromNode(TreeNode node, long remaining) {
    if (node == null) return 0;
    int count = (remaining == node.val) ? 1 : 0;
    count += countFromNode(node.left, remaining - node.val);
    count += countFromNode(node.right, remaining - node.val);
    return count;
}

What should a senior engineer know?

At the National Bank of India, Rajesh modeled a chain of linked transactions as a tree where each node carries an amount. Path Sum checked whether a full origin-to-terminal chain matched a flagged amount. Path Sum III counted every downward sub-chain summing to that amount, because structured laundering hides the target inside a longer chain. The prefix-sum map with correct backtracking made scanning large transaction trees fast and accurate.