# LeetCode 437: Path Sum III

## Problem Restatement

We are given the root of a binary tree and an integer `targetSum`.

We need to count how many paths have node values that add up to `targetSum`.

A valid path:

| Rule | Meaning |
|---|---|
| Can start anywhere | It does not have to start at the root |
| Can end anywhere | It does not have to end at a leaf |
| Must go downward | It can only move from parent to child |

So this path is valid:

```text
parent -> child -> grandchild
```

But this path is not valid:

```text
left child -> parent -> right child
```

because it moves upward.

The official problem asks for the number of downward paths whose sum equals `targetSum`. The tree can be empty, and node values may be large or negative.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root` of a binary tree and integer `targetSum` |
| Output | Number of valid downward paths |
| Path start | Any node |
| Path end | Any node below the start node, including itself |
| Empty tree | Return `0` |

The node class is usually:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```

## Examples

Example 1:

```python
root = [10, 5, -3, 3, 2, None, 11, 3, -2, None, 1]
targetSum = 8
```

The answer is:

```python
3
```

The three paths are:

```text
5 -> 3
5 -> 2 -> 1
-3 -> 11
```

Example 2:

```python
root = [5, 4, 8, 11, None, 13, 4, 7, 2, None, None, 5, 1]
targetSum = 22
```

The answer is:

```python
3
```

Example 3:

```python
root = None
targetSum = 0
```

The answer is:

```python
0
```

There are no nodes, so there are no paths.

## First Thought: Start DFS From Every Node

A direct approach is:

1. Pick every node as a possible path start.
2. From that node, try every downward path.
3. Count paths whose sum equals `targetSum`.

This works, but it can revisit the same subtree many times.

For a skewed tree, the time complexity can become:

```python
O(n^2)
```

We need to count all possible downward paths while visiting each node only once.

## Key Insight

This problem is a tree version of subarray sum with prefix sums.

Suppose we are walking from the root to the current node and the running sum is:

```python
current_sum
```

We want to know whether there is an earlier point on the same root-to-current path where the prefix sum was:

```python
current_sum - targetSum
```

Why?

If:

```python
current_sum - old_prefix_sum = targetSum
```

then the path after that old prefix and ending at the current node has sum `targetSum`.

Rearrange:

```python
old_prefix_sum = current_sum - targetSum
```

So during DFS, we keep a hash map:

```python
prefix_count[prefix_sum] = frequency
```

This map stores prefix sums only along the current root-to-node path.

## Algorithm

Initialize:

```python
prefix_count = {0: 1}
```

The prefix sum `0` handles paths that start at the root.

Run DFS with:

```python
dfs(node, current_sum)
```

For each node:

1. Add the node value to `current_sum`.
2. Count how many earlier prefixes equal `current_sum - targetSum`.
3. Add the current prefix sum to the hash map.
4. Recurse into left and right children.
5. Remove the current prefix sum from the hash map before returning.

The last step is important. Prefix sums from one branch must not affect another branch.

## Correctness

At any point during DFS, `prefix_count` contains exactly the prefix sums on the current path from the root to the parent of the current node.

When we visit a node, we update `current_sum` to include that node.

A downward path ending at the current node has sum `targetSum` exactly when there exists an earlier prefix sum `p` such that:

```python
current_sum - p == targetSum
```

This is equivalent to:

```python
p == current_sum - targetSum
```

So `prefix_count[current_sum - targetSum]` gives exactly the number of valid paths ending at the current node.

After counting paths ending at the current node, we add `current_sum` to `prefix_count` before processing children. This allows child paths to start at the current node or above it.

After processing both children, we decrement the current prefix sum. This restores the hash map to its previous state before returning to the parent, so sibling branches do not share invalid prefix sums.

Because the DFS visits every node and counts exactly the valid paths ending at that node, the final total is the number of all valid downward paths.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | Hash map and recursion stack follow the current root-to-node path |

Here, `n` is the number of nodes.

`h` is the height of the tree.

In the worst case, `h = n`.

## Implementation

```python
from collections import defaultdict

class Solution:
    def pathSum(self, root: 'Optional[TreeNode]', targetSum: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1

        def dfs(node: 'Optional[TreeNode]', current_sum: int) -> int:
            if not node:
                return 0

            current_sum += node.val

            total = prefix_count[current_sum - targetSum]

            prefix_count[current_sum] += 1

            total += dfs(node.left, current_sum)
            total += dfs(node.right, current_sum)

            prefix_count[current_sum] -= 1

            return total

        return dfs(root, 0)
```

## Code Explanation

We use a hash map to count prefix sums:

```python
prefix_count = defaultdict(int)
prefix_count[0] = 1
```

The initial `0` means there is one empty prefix before the root.

The DFS receives the current running sum:

```python
def dfs(node, current_sum):
```

If the node is missing, it contributes no paths:

```python
if not node:
    return 0
```

We include the current node:

```python
current_sum += node.val
```

Now we count paths ending exactly at this node:

```python
total = prefix_count[current_sum - targetSum]
```

Then we add the current prefix before going downward:

```python
prefix_count[current_sum] += 1
```

Now the left and right children can use this prefix:

```python
total += dfs(node.left, current_sum)
total += dfs(node.right, current_sum)
```

After both children are processed, we backtrack:

```python
prefix_count[current_sum] -= 1
```

This removes the current node’s prefix from the active path.

Finally, the DFS returns how many valid paths were found in this subtree.

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(
        10,
        TreeNode(
            5,
            TreeNode(
                3,
                TreeNode(3),
                TreeNode(-2),
            ),
            TreeNode(
                2,
                None,
                TreeNode(1),
            ),
        ),
        TreeNode(
            -3,
            None,
            TreeNode(11),
        ),
    )

    assert s.pathSum(root, 8) == 3

    root = TreeNode(
        5,
        TreeNode(
            4,
            TreeNode(
                11,
                TreeNode(7),
                TreeNode(2),
            ),
        ),
        TreeNode(
            8,
            TreeNode(13),
            TreeNode(
                4,
                TreeNode(5),
                TreeNode(1),
            ),
        ),
    )

    assert s.pathSum(root, 22) == 3

    assert s.pathSum(None, 0) == 0

    root = TreeNode(1, TreeNode(-1), TreeNode(1))
    assert s.pathSum(root, 0) == 1

    root = TreeNode(0, TreeNode(0), TreeNode(0))
    assert s.pathSum(root, 0) == 5

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks paths starting below root |
| Target `22` example | Checks longer downward paths |
| Empty tree | Checks no-node case |
| Negative value | Checks prefix sums with subtraction |
| Zero values | Checks multiple overlapping valid paths |