This problem asks you to count how many paths in a binary tree have a sum equal to a given target value. The path:

• can start at any node
• can end at any node
• must go downward only (parent → child)
• does not have to start at the root
• does not have to end at a leaf

Example:

Input:
root = [10,5,-3,3,2,null,11,3,-2,null,1]
targetSum = 8

Output: 3

The three valid paths are:

5 → 3
5 → 2 → 1
-3 → 11

---

Problem Requirements and Observations

Important characteristics:

• Paths must follow parent-to-child direction
• Multiple overlapping paths may exist
• Brute-force checking all paths leads to O(n²) time

Constraints:

• Tree size can reach 100,000 nodes
• Efficiency matters

---

Logic Explained in Simple English

There are two common ways to solve this:

---

Approach A: Simple Recursive Counting (slower)

For every node:

1. Count paths starting from this node that sum to target
2. Recursively repeat for left child
3. Recursively repeat for right child

But this approach is slow because:

• For each node, we explore paths downward
• Worst-case time becomes O(n²)

This may still pass smaller trees, but not optimal.

---

Approach B: Prefix Sum with HashMap (fast and elegant)

Think of it like prefix sums in arrays:

• As we move down the tree, we track the running sum.
• If currentSum - targetSum has appeared before,
  then we found a valid path ending at this node.

We store counts of prefix sums in a HashMap:

1. Start with map {0:1} meaning before traversal sum = 0 occurred once
2. At each node:
   • Update running sum
   • Check how many times (runningSum - target) appeared
   • Add that to result count
3. Recurse left and right
4. Decrement running sum count when backtracking

Why this works:

• It counts all valid start points automatically
• No need to restart at every node
• Works in O(n) time

---

Step-by-Step Algorithm (Prefix Sum Method)

1. Create a global counter
2. Create a HashMap storing {prefixSum : frequency}
3. Initialize map with {0 : 1}
4. Perform DFS:
   • Add current node value to runningSum
   • Compute runningSum - target
   • Add frequency of that value to result
   • Increment frequency of runningSum in map
   • Recurse to left and right
   • Decrement frequency when backtracking
5. Return result

---

Java Implementation (Optimal)

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0L, 1);
        return dfs(root, 0L, targetSum, prefixCount);
    }

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

        runningSum += node.val;
        int count = prefixCount.getOrDefault(runningSum - targetSum, 0);

        prefixCount.put(runningSum, prefixCount.getOrDefault(runningSum, 0) + 1);

        count += dfs(node.left, runningSum, targetSum, prefixCount);
        count += dfs(node.right, runningSum, targetSum, prefixCount);

        prefixCount.put(runningSum, prefixCount.get(runningSum) - 1);

        return count;
    }
}

---

Dry Run Example

Tree:

      10
     /  \
    5   -3
   / \    \
  3   2    11
 / \   \
3  -2   1

TargetSum = 8

prefixCount starts as:

{0:1}
runningSum = 0

Visit 10

runningSum = 10
10 – 8 = 2 → not in map
prefixCount = {0:1, 10:1}

Visit 5

runningSum = 15
15 – 8 = 7 → not in map
prefixCount = {0:1, 10:1, 15:1}

Visit 3

runningSum = 18
18 – 8 = 10 → prefixCount[10] = 1
count = 1 (path found: 5 → 3)
prefixCount = {0:1, 10:1, 15:1, 18:1}

Visit 3

runningSum = 21
21 – 8 = 13 → none
prefixCount = {0:1,10:1,15:1,18:1,21:1}

Backtrack…

Visit -2

runningSum = 16
16 – 8 = 8 → none
prefixCount updated accordingly

Backtrack…

Visit 2

runningSum = 17
17 – 8 = 9 → none
prefixCount updated

Visit 1

runningSum = 18
18 – 8 = 10 → found another path (5 → 2 → 1)

Backtrack…

Visit -3

runningSum = 7
7 – 8 = -1 → none

Visit 11

runningSum = 18
18 – 8 = 10 → another match ( -3 → 11 )

Total paths found = 3

---

Time and Space Complexity

Time Complexity

O(n)
Reason:

• Each node visited once
• HashMap operations are constant time

Space Complexity

O(h) average, O(n) worst case
h = tree height
Due to recursion and HashMap storage of prefix sums

---

Common Mistakes and How to Avoid Them

Mistake 1: Only counting root-to-leaf paths

This problem allows paths starting anywhere.

Mistake 2: Forgetting to backtrack prefix sum count

Backtracking is necessary to isolate path scopes.

Mistake 3: Using int instead of long for running sums

Sums may overflow.

Mistake 4: Restarting DFS from every node

Leads to O(n²), too slow for large trees.

Mistake 5: Confusing with Path Sum II

Path Sum II requires listing root-to-leaf paths — this problem does not.