# Path Sum III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/path-sum-iii)
Canonical: https://scaleengineer.com/dsa/problems/path-sum-iii
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Zepto](https://scaleengineer.com/companies/zepto), [NetApp](https://scaleengineer.com/companies/netapp)
---
## Problem
Given the `root` of a binary tree and an integer `targetSum`, return _the number of paths where the sum of the values along the path equals_ `targetSum`.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

**Example 1:**

![](https://assets.glich.co/dsa/path-sum-iii/image0.jpg) 

**Input:** root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
**Output:** 3
**Explanation:** The paths that sum to 8 are shown.

**Example 2:**

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

**Constraints:**

* The number of nodes in the tree is in the range `[0, 1000]`.
* `-109 <= Node.val <= 109`
* `-1000 <= targetSum <= 1000`

# Approaches
## Brute Force using Double Recursion
This approach is a straightforward, brute-force solution that directly translates the problem statement into a recursive algorithm. It considers every possible starting node for a path. For each node in the tree, it initiates a separate downward traversal to find all paths starting from that node that sum up to the `targetSum`. The final result is the sum of counts from all possible starting nodes.
**Time:** O(N^2) in the worst case (a skewed tree) and O(N log N) in the average case (a balanced tree), where N is the number of nodes. For each of the N nodes, we traverse its subtree, which takes O(H) time, where H is the height of the subtree. · **Space:** O(N) in the worst case (a skewed tree) and O(log N) in the average case (a balanced tree). The space is determined by the maximum depth of the recursion stack.
**Pros:** Relatively simple to conceptualize and implement.; The logic directly follows the problem's definition without complex data structures.
**Cons:** Highly inefficient due to a large number of redundant calculations. The sum for the same subpath is computed multiple times.; The time complexity is quadratic in the worst-case scenario, which can be too slow for large trees.
### Explanation
The solution uses a pair of recursive functions. The main function, `pathSum`, iterates through all nodes in the tree. For each node, it treats it as a potential starting point for a valid path. It calls a helper function, `countPathsFromNode`, to count all valid paths that begin at this specific node and extend downwards.

The `pathSum` function's result for a given node is the sum of:
1.  The number of valid paths starting at the current node (calculated by `countPathsFromNode`).
2.  The number of valid paths that exist entirely within the left subtree (found by a recursive call to `pathSum` on the left child).
3.  The number of valid paths that exist entirely within the right subtree (found by a recursive call to `pathSum` on the right child).

This method ensures that every possible downward path is considered. To prevent integer overflow with potentially large node values and path lengths, path sums are accumulated using a `long` data type.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        // Count paths starting from the current root, plus paths in left/right subtrees.
        return countPathsFromNode(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }
    
    // Helper function to count paths starting from a given node that sum to the target.
    // Note: We use a long for the current sum to avoid overflow.
    private int countPathsFromNode(TreeNode node, long targetSum) {
        if (node == null) {
            return 0;
        }
        
        int count = 0;
        // Check if the current node itself completes a path.
        if (node.val == targetSum) {
            count = 1;
        }
        
        // Continue the path downwards and see if longer paths also sum to the target.
        long remainingSum = targetSum - node.val;
        count += countPathsFromNode(node.left, remainingSum);
        count += countPathsFromNode(node.right, remainingSum);
        
        return count;
    }
}
```
### Algorithm
The overall strategy involves a double recursion.
1.  The main recursive function, `pathSum(node, targetSum)`, traverses every node in the tree.
2.  For each `node`, it calculates the total number of valid paths by summing up three values:
    *   The number of valid paths that start at the current `node`.
    *   The number of valid paths found in the left subtree (by recursively calling `pathSum` on `node.left`).
    *   The number of valid paths found in the right subtree (by recursively calling `pathSum` on `node.right`).
3.  A helper function, `countPathsFromNode(node, currentSum, targetSum)`, is used to find the number of paths that start at a specific `node` and sum to `targetSum`.
4.  This helper function traverses downwards from the given `node`.
    *   It takes the current node, the sum accumulated so far on the current path (`currentSum`), and the `targetSum`.
    *   If `currentSum + node.val` equals `targetSum`, a valid path is found.
    *   It continues to search for longer paths by recursively calling itself on the left and right children with the updated `currentSum`.

## Optimized Approach using Prefix Sum
This optimized approach leverages the concept of prefix sums to solve the problem in a single pass. As we traverse the tree from the root downwards, we maintain the sum of the path from the root to the current node (the prefix sum). The sum of any path between an ancestor node `A` and a descendant node `B` can be calculated as `prefixSum(B) - prefixSum(A)`. We are looking for paths where this difference equals `targetSum`.

By rearranging the equation to `prefixSum(A) = prefixSum(B) - targetSum`, we can see that for each node `B`, we just need to find how many of its ancestors `A` have a prefix sum that matches this required value. A hash map is used to efficiently store and retrieve the frequencies of prefix sums encountered on the current path from the root.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once, and the hash map operations (get, put) take O(1) time on average. · **Space:** O(H), where H is the height of the tree. This space is used by both the recursion stack and the hash map. In the worst case of a skewed tree, H = N, leading to O(N) space. For a balanced tree, H = log N, leading to O(log N) space.
**Pros:** Highly efficient, with a linear time complexity as it traverses the tree only once.; Avoids redundant calculations by storing intermediate results (prefix sums) in a hash map.
**Cons:** The logic, particularly the concept of prefix sums in a tree and the necessity of backtracking, is more complex to understand.; Requires additional space for the hash map, which can be proportional to the height of the tree.
### Explanation
This method performs a single depth-first traversal (DFS) of the tree. A hash map, `prefixSumCount`, is used to keep track of the cumulative sums from the root to the nodes on the current path and their frequencies.

For any node `curr`, the path sum from the root to `curr` is `currentSum`. If there was a previous node `prev` on the same path from the root with a path sum of `prevSum`, then the sum of the path from `prev` to `curr` is `currentSum - prevSum`. We want this to be equal to `targetSum`, so `currentSum - prevSum = targetSum`, which implies `prevSum = currentSum - targetSum`.

So, as we traverse to a node `curr`, we calculate its `currentSum`. Then, we check the hash map to see how many times we have previously seen a prefix sum of `currentSum - targetSum`. This count gives us the number of valid paths ending at the current node `curr`.

After processing a node, we add its `currentSum` to the map before visiting its children. After the recursive calls to its children return (i.e., after exploring its entire subtree), we must remove its `currentSum` from the map (backtrack). This is essential because the prefix sums of one subtree should not be available to its sibling subtree.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.HashMap;
import java.util.Map;

class Solution {
    int count = 0;
    int k;
    Map<Long, Integer> prefixSumCount = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        this.k = targetSum;
        // The map stores <prefix sum, frequency>.
        // A prefix sum of 0 has a frequency of 1 to handle paths that start from the root.
        prefixSumCount.put(0L, 1);
        dfs(root, 0L);
        return count;
    }

    private void dfs(TreeNode node, long currentSum) {
        if (node == null) {
            return;
        }

        // 1. Update current path sum
        currentSum += node.val;

        // 2. Check if (currentSum - k) exists in the map
        // This is the core logic. If it exists, it means there's a path
        // from some ancestor to the current node that sums to k.
        count += prefixSumCount.getOrDefault(currentSum - k, 0);

        // 3. Update the map with the current prefix sum for descendant nodes
        prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);

        // 4. Recurse for children
        dfs(node.left, currentSum);
        dfs(node.right, currentSum);

        // 5. Backtrack: remove the current prefix sum from the map
        // This is crucial so that prefix sums from one branch don't affect sibling branches.
        prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1);
    }
}
```
### Algorithm
1.  Initialize a global `count` to 0 and a `HashMap<Long, Integer>` named `prefixSumCount` to store the frequencies of prefix sums encountered.
2.  Add an initial entry `{0L: 1}` to `prefixSumCount`. This is a crucial base case that handles paths starting from the root node.
3.  Define a recursive DFS function, `dfs(node, currentSum)`.
4.  Inside `dfs`:
    a. If `node` is null, return.
    b. Update the `currentSum` by adding the current `node.val`. The `currentSum` represents the prefix sum from the root to the current node.
    c. Calculate the `complement` sum needed: `complement = currentSum - targetSum`. Check if this `complement` exists as a key in `prefixSumCount`. If it does, it means there are `prefixSumCount.get(complement)` paths ending at the current node that sum to `targetSum`. Add this number to the global `count`.
    d. Update the map for the current path: Increment the frequency of `currentSum` in `prefixSumCount`.
    e. Recursively call `dfs` for the left and right children.
    f. **Backtrack:** After the recursive calls for the children return, decrement the frequency of `currentSum` in `prefixSumCount`. This step is vital to ensure that prefix sums from one branch do not interfere with calculations in a sibling branch.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int PathSum ( TreeNode root , int targetSum ) { Dictionary < long , int > cnt = new Dictionary < long , int >(); int Dfs ( TreeNode node , long s ) { if ( node == null ) { return 0 ; } s += node . val ; int ans = cnt . GetValueOrDefault ( s - targetSum , 0 ); cnt [ s ] = cnt . GetValueOrDefault ( s , 0 ) + 1 ; ans += Dfs ( node . left , s ); ans += Dfs ( node . right , s ); cnt [ s ]--; return ans ; } cnt [ 0 ] = 1 ; return Dfs ( root , 0 ); } }
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map < Long , Integer > cnt = new HashMap <>(); private int targetSum ; public int pathSum ( TreeNode root , int targetSum ) { cnt . put ( 0L , 1 ); this . targetSum = targetSum ; return dfs ( root , 0 ); } private int dfs ( TreeNode node , long s ) { if ( node == null ) { return 0 ; } s += node . val ; int ans = cnt . getOrDefault ( s - targetSum , 0 ); cnt . merge ( s , 1 , Integer: : sum ); ans += dfs ( node . left , s ); ans += dfs ( node . right , s ); cnt . merge ( s , - 1 , Integer: : sum ); return ans ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number} */ var pathSum =
  function (root, targetSum) {
    const cnt = new Map();
    const dfs = (node, s) => {
      if (!node) {
        return 0;
      }
      s += node.val;
      let ans = cnt.get(s - targetSum) || 0;
      cnt.set(s, (cnt.get(s) || 0) + 1);
      ans += dfs(node.left, s);
      ans += dfs(node.right, s);
      cnt.set(s, cnt.get(s) - 1);
      return ans;
    };
    cnt.set(0, 1);
    return dfs(root, 0);
  };

```

### CPP

```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 , int > cnt ; cnt [ 0 ] = 1 ; function < int ( TreeNode * , long ) > dfs = [ & ]( TreeNode * node , long s ) -> int { if ( ! node ) return 0 ; s += node -> val ; int ans = cnt [ s - targetSum ]; ++ cnt [ s ]; ans += dfs ( node -> left , s ) + dfs ( node -> right , s ); -- cnt [ s ]; return ans ; }; return dfs ( root , 0 ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def pathSum ( self , root : Optional [ TreeNode ], targetSum : int ) -> int : def dfs ( node , s ): if node is None : return 0 s += node . val ans = cnt [ s - targetSum ] cnt [ s ] += 1 ans += dfs ( node . left , s ) ans += dfs ( node . right , s ) cnt [ s ] -= 1 return ans cnt = Counter ({ 0 : 1 }) return dfs ( root , 0 )
```