DFS | PrefixSum | C++
To solve the problem of finding the number of paths in a binary tree that sum to a given targetSum, we can use a prefix sum approach combined with depth-first s
To solve the problem of finding the number of paths in a binary tree that sum to a given `targetSum`, we can use a **prefix sum** approach combined with **depth-first search (DFS)**. This approach efficiently counts the number of valid paths by keeping track of the cumulative sum of values along the current path and checking if any prefix sum difference matches the `targetSum`.

---

# Approach
---

1. **Prefix Sum:**
- Use a hash map (`unordered_map`) to store the frequency of prefix sums encountered during the traversal. 
- Initialize the map with {`0: 1`} to handle the case where the current path itself sums to `targetSum`.

2. **DFS Traversal:**

- Traverse the tree using DFS.

- At each node, update the current cumulative sum (`currentSum`).

- Check if (`currentSum - targetSum`) exists in the prefix sum map. If it does, increment the count of valid paths by the frequency of (`currentSum - targetSum`).

- Update the prefix sum map with the current cumulative sum.

- Recursively traverse the left and right subtrees.

- After traversing the left and right subtrees, backtrack by decrementing the frequency of the current cumulative sum in the prefix sum map.

3. **Base Case:**

- If the current node is `nullptr`, return 0.

4. **Result:**

- The total count of valid paths is returned.
---

# Complexity
---

- **Time Complexity:** O(N), where N is the number of nodes in the tree. Each node is visited once.

- **Space Complexity:** O(N), due to the recursion stack and the prefix sum map.
---

# Code
```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> prefixSumCount; // Use long long for prefix sums
        prefixSumCount[0] = 1; // Initialize with {0: 1}
        return dfs(root, 0, targetSum, prefixSumCount);
    }

private:
    int dfs(TreeNode* node, long long currentSum, int targetSum, unordered_map<long long, int>& prefixSumCount) {
        if (node == nullptr) {
            return 0; // Base case: no nodes to process
        }

        // Update the current cumulative sum
        currentSum += node->val;

        // Check if (currentSum - targetSum) exists in the prefix sum map
        int numPaths = prefixSumCount[currentSum - targetSum];

        // Update the prefix sum map with the current cumulative sum
        prefixSumCount[currentSum]++;

        // Recursively traverse the left and right subtrees
        numPaths += dfs(node->left, currentSum, targetSum, prefixSumCount);
        numPaths += dfs(node->right, currentSum, targetSum, prefixSumCount);

        // Backtrack: decrement the frequency of the current cumulative sum
        prefixSumCount[currentSum]--;

        return numPaths;
    }
};
```

---

# Example WalkThrough:
---

**Input Tree:**
```
        10
       /  \
      5    -3
     / \    \
    3   2    11
   / \   \
  3  -2   1
```

**Target Sum: `8`**

---

1. **Initialize Prefix Sum Map:**
- Start with a prefix sum map: `{0: 1}`.
   - This is because a cumulative sum of `0` has been seen once (before starting the traversal).

2. **Start DFS Traversal:**

---


**Step 1: Traverse Root Node (10):**

- **Current Node: `10`**

- **Current Cumulative `Sum: 0 + 10 = 10`**

- **Check for Valid Path:**

     - Calculate `(currentSum - targetSum) = 10 - 8 = 2`.

     - Is `2` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**

    - Add `10` to the map: `{0: 1, 10: 1}`.

- **Recurse to Left Child (5).**

---

**Step 2: Traverse Node (5):**

- **Current Node: 5**

- **Current Cumulative Sum: `10 + 5 = 15`**

- **Check for Valid Path:**
    - Calculate `(currentSum - targetSum) = 15 - 8 = 7`.

    - Is `7` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**

    - Add `15` to the map: `{0: 1, 10: 1, 15: 1}`.

- **Recurse to Left Child (3).**
---


**Step 3: Traverse Node (3):**

- **Current Node: 3**

- **Current Cumulative Sum: `15 + 3 = 18`**

- **Check for Valid Path:**
    - Calculate `(currentSum - targetSum) = 18 - 8 = 10`.

    - Is `10` in the prefix sum map? **Yes** (frequency = 1).

    - Valid Path Found: Increment the count of valid paths by `1`.

- **Update Prefix Sum Map:**
    - Add `18` to the map: `{0: 1, 10: 1, 15: 1, 18: 1}`.

- **Recurse to Left Child (3).**

---

**Step 4: Traverse Node (3):**

- **Current Node: 3**

- **Current Cumulative Sum: `18 + 3 = 21`**

- **Check for Valid Path:**

    - Calculate `(currentSum - targetSum) = 21 - 8 = 13`.

    - Is `13` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**

    - Add `21` to the map: `{0: 1, 10: 1, 15: 1, 18: 1, 21: 1}`.

- **Recurse to Left Child (null).**

---

**Step 5: Backtrack to Node (3):**

- **Current Node: 3**

- **Remove Current Cumulative Sum from Map:**
    - Remove `21` from the map: `{0: 1, 10: 1, 15: 1, 18: 1}`.

- **Recurse to Right Child (-2).**

---

**Step 6: Traverse Node (-2):**

- **Current Node: -2**

- **Current Cumulative Sum: `18 + (-2) = 16`**

- **Check for Valid Path:**

    - Calculate `(currentSum - targetSum) = 16 - 8 = 8`.

    - Is `8` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**

    - Add `16` to the map: `{0: 1, 10: 1, 15: 1, 18: 1, 16: 1}`.
    

- **Recurse to Left Child (null)**.

---

**Step 7: Backtrack to Node (-2):**

- **Current Node: -2**

- **Remove Current Cumulative Sum from Map:**

    - Remove `16` from the map: `{0: 1, 10: 1, 15: 1, 18: 1}`.

- **Recurse to Right Child (null).**

---

**Step 8: Backtrack to Node (3):**

- **Current Node: 3**
- **Remove Current Cumulative Sum from Map:**
    - Remove `18` from the map: `{0: 1, 10: 1, 15: 1}`.

- **Recurse to Right Child (2).**

---

**Step 9: Traverse Node (2):**

- **Current Node: 2**
- **Current Cumulative Sum: `15 + 2 = 17`**
- **Check for Valid Path:**
    - Calculate `(currentSum - targetSum) = 17 - 8 = 9`.

    - Is `9` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**
    - Add `17` to the map: `{0: 1, 10: 1, 15: 1, 17: 1}`.

- **Recurse to Left Child (null).**

---


**Step 10: Backtrack to Node (2):**
- **Current Node: 2**
- **Remove Current Cumulative Sum from Map:**
   - Remove `17` from the map: `{0: 1, 10: 1, 15: 1}`.

- **Recurse to Right Child (1).**
---


**Step 11: Traverse Node (1):**

- **Current Node: 1**

- **Current Cumulative Sum: `15 + 1 = 16`**

- **Check for Valid Path:**

    - Calculate `(currentSum - targetSum) = 16 - 8 = 8`.

    - Is `8` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**

   - Add `16` to the map: `{0: 1, 10: 1, 15: 1, 16: 1}`.

- **Recurse to Left Child (null).**
---

**Step 12: Backtrack to Node (1):**

- **Current Node: 1**

- **Remove Current Cumulative Sum from Map:**

     - Remove `16` from the map: `{0: 1, 10: 1, 15: 1}`.


- **Recurse to Right Child (null).**
---

**Step 13: Backtrack to Node (5):**

- **Current Node: 5**

- **Remove Current Cumulative Sum from Map:**

   - Remove `15` from the map: `{0: 1, 10: 1}`.

- **Recurse to Right Child (-3).**
---

**Step 14: Traverse Node (-3):**
- **Current Node: -3**

- **Current Cumulative Sum: `10 + (-3) = 7`**

- **Check for Valid Path:**
    - Calculate `(currentSum - targetSum) = 7 - 8 = -1`.

    - Is `-1` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**

    - Add `7` to the map: `{0: 1, 10: 1, 7: 1}`.

- **Recurse to Left Child (null).**
---

**Step 15: Backtrack to Node (-3):**

- **Current Node: -3**

- **Remove Current Cumulative Sum from Map:**

    - Remove `7` from the map: `{0: 1, 10: 1}`.

- **Recurse to Right Child (11).**
---

**Step 16: Traverse Node (11):**
- **Current Node: 11**

- **Current Cumulative Sum: `10 + 11 = 21`**

- **Check for Valid Path:**

    - Calculate `(currentSum - targetSum) = 21 - 8 = 13`.
    - Is `13` in the prefix sum map? **No**.

- **Update Prefix Sum Map:**

    - Add `21` to the map: `{0: 1, 10: 1, 21: 1}`.

- **Recurse to Left Child (null).**
---

**Step 17: Backtrack to Node (11):**
- **Current Node: 11**

- **Remove Current Cumulative Sum from Map:**

    - Remove `21` from the map: `{0: 1, 10: 1}`.
- **Recurse to Right Child (null).**
---

**Step 18: Backtrack to Node (10):**

- **Current Node: 10**

- **Remove Current Cumulative Sum from Map:**
    - Remove `10` from the map: `{0: 1}`.
---

The total number of valid paths is `3`:

1. `5 → 3`
2. `5 → 2 → 1`
3. `-3 → 11`


---

![upvote.jpg](https://assets.leetcode.com/users/images/020c1a29-900f-4f2f-aea2-98d019dc6bb3_1741522131.142132.jpeg)


['C++']