# LeetCode 113: Path Sum II

## Problem Restatement

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

We need to return all root-to-leaf paths where the sum of node values equals `targetSum`.

Each returned path must:

1. Start at the root.
2. End at a leaf.
3. Have node values summing to `targetSum`.

The official problem asks for all root-to-leaf paths whose sum equals the target. ([leetcode.com](https://leetcode.com/problems/path-sum-ii/?utm_source=chatgpt.com))

For this tree:

```text
        5
      /   \
     4     8
    /     / \
   11    13  4
  /  \      / \
 7    2    5   1
```

and:

```python
targetSum = 22
```

The valid paths are:

```python
[
    [5, 4, 11, 2],
    [5, 8, 4, 5]
]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root` and `targetSum` |
| Output | A list of valid root-to-leaf paths |
| Valid path | Must start at root and end at a leaf |
| Leaf | Node with no children |
| Empty tree | Return `[]` |

LeetCode gives the `TreeNode` class:

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

The function shape is:

```python
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> list[list[int]]:
        ...
```

## Examples

Consider:

```text
        5
      /   \
     4     8
    /     / \
   11    13  4
  /  \      / \
 7    2    5   1
```

with:

```python
targetSum = 22
```

One root-to-leaf path is:

```text
5 -> 4 -> 11 -> 2
```

Its sum is:

```python
22
```

Another valid path is:

```text
5 -> 8 -> 4 -> 5
```

Its sum is also:

```python
22
```

So the answer is:

```python
[
    [5, 4, 11, 2],
    [5, 8, 4, 5]
]
```

Now consider:

```text
   1
  / \
 2   3
```

with:

```python
targetSum = 5
```

The root-to-leaf paths are:

```text
1 -> 2 = 3
1 -> 3 = 4
```

No path sums to `5`, so the answer is:

```python
[]
```

## First Thought: Explore Every Root-to-Leaf Path

This problem is similar to LeetCode 112.

We still need to explore all root-to-leaf paths.

The difference is:

- LeetCode 112 asks whether at least one valid path exists.
- This problem asks us to return every valid path.

That means we must keep track of the current path while doing DFS.

## Key Insight

During DFS, maintain:

1. The current path.
2. The remaining sum.

At each node:

- Add the node value to the path.
- Subtract the node value from the remaining target.

When we reach a leaf:

- If the remaining target equals the leaf value, store a copy of the current path.

After exploring a subtree, remove the current node from the path before returning.

This removal step is called backtracking.

Without backtracking, values from one branch would incorrectly remain in the path for another branch.

## Algorithm

Create:

```python
ans = []
path = []
```

Define a recursive DFS function.

For each node:

1. If the node is `None`, return.
2. Add the node value to `path`.
3. If the node is a leaf:
   1. Check whether the path sum matches the target.
   2. If yes, append a copy of `path` to `ans`.
4. Otherwise:
   1. Continue DFS into the left subtree.
   2. Continue DFS into the right subtree.
5. Remove the current node from `path`.

The recursive calls use:

```python
remaining - node.val
```

## Correctness

The DFS explores every root-to-leaf path exactly once.

At each recursive call, `path` contains exactly the node values from the root to the current node, in order. The variable `remaining` stores the target sum still needed from the current node downward.

When the algorithm reaches a leaf, the current path is complete. If the remaining target equals the leaf value, then the sum of all values in `path` equals `targetSum`, so the path is valid and is added to the answer list.

The recursive calls explore both left and right subtrees, so no possible root-to-leaf path is missed.

After finishing a subtree, the algorithm removes the current node from `path`. Therefore, the path state is restored correctly before exploring another branch. This guarantees that paths from different branches do not interfere with each other.

Thus, every valid root-to-leaf path is added exactly once, and no invalid path is included.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` for traversal, plus path copying cost | Every node is visited once |
| Space | `O(h)` recursion stack, excluding output | DFS follows one root-to-leaf path |

Here:

- `n` is the number of nodes.
- `h` is the tree height.

Copying valid paths costs additional time proportional to path length.

## Implementation

```python
from typing import Optional

# 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) -> list[list[int]]:
        ans = []
        path = []

        def dfs(node: Optional[TreeNode], remaining: int) -> None:
            if node is None:
                return

            path.append(node.val)

            if node.left is None and node.right is None:
                if remaining == node.val:
                    ans.append(path[:])
            else:
                dfs(node.left, remaining - node.val)
                dfs(node.right, remaining - node.val)

            path.pop()

        dfs(root, targetSum)

        return ans
```

## Code Explanation

The answer list stores all valid paths:

```python
ans = []
```

The `path` list stores the current DFS path:

```python
path = []
```

The DFS helper receives:

```python
node
remaining
```

Handle the empty subtree:

```python
if node is None:
    return
```

Add the current node to the path:

```python
path.append(node.val)
```

Check whether the current node is a leaf:

```python
if node.left is None and node.right is None:
```

If the remaining target equals the current value, the path is valid:

```python
if remaining == node.val:
    ans.append(path[:])
```

`path[:]` creates a copy.

Without copying, later modifications would change stored answers.

For non-leaf nodes, continue DFS:

```python
dfs(node.left, remaining - node.val)
dfs(node.right, remaining - node.val)
```

Finally, remove the current node before returning:

```python
path.pop()
```

This restores the path for the parent call.

## Testing

```python
from typing import Optional

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) -> list[list[int]]:
        ans = []
        path = []

        def dfs(node: Optional[TreeNode], remaining: int) -> None:
            if node is None:
                return

            path.append(node.val)

            if node.left is None and node.right is None:
                if remaining == node.val:
                    ans.append(path[:])
            else:
                dfs(node.left, remaining - node.val)
                dfs(node.right, remaining - node.val)

            path.pop()

        dfs(root, targetSum)

        return ans

def run_tests():
    s = Solution()

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

    assert sorted(s.pathSum(root1, 22)) == sorted([
        [5, 4, 11, 2],
        [5, 8, 4, 5],
    ])

    root2 = TreeNode(1, TreeNode(2), TreeNode(3))
    assert s.pathSum(root2, 5) == []

    root3 = None
    assert s.pathSum(root3, 0) == []

    root4 = TreeNode(1)
    assert s.pathSum(root4, 1) == [[1]]

    root5 = TreeNode(
        -2,
        None,
        TreeNode(-3),
    )
    assert s.pathSum(root5, -5) == [[-2, -3]]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example with two valid paths | Confirms multiple paths are collected |
| No valid path | Confirms empty result |
| Empty tree | Confirms base case |
| Single-node valid path | Confirms root can also be a leaf |
| Negative values | Confirms subtraction works correctly |