# LeetCode 112: Path Sum

## Problem Restatement

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

We need to return `True` if the tree has at least one root-to-leaf path whose node values add up to `targetSum`. A leaf is a node with no children. If no such path exists, return `False`. The official problem uses this same root-to-leaf path requirement.

For this tree:

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

and:

```python
targetSum = 22
```

There is a valid path:

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

The sum is:

```python
5 + 4 + 11 + 2 = 22
```

So the answer is:

```python
True
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root`, the root of a binary tree, and `targetSum` |
| Output | `True` if a valid root-to-leaf path exists, otherwise `False` |
| Valid path | Must start at the root and end at a leaf |
| Leaf | A node with no left child and no right child |
| Empty tree | Return `False` |

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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        ...
```

## Examples

Consider:

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

with:

```python
targetSum = 22
```

One root-to-leaf path is:

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

Its sum is:

```python
22
```

So the answer is:

```python
True
```

Now consider:

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

with:

```python
targetSum = 5
```

The root-to-leaf paths are:

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

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

```python
False
```

For an empty tree:

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

The answer is:

```python
False
```

An empty tree has no root-to-leaf paths.

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

The direct idea is to explore every path from the root down to a leaf.

For each path, compute the sum of its node values.

If any path sum equals `targetSum`, return `True`.

This naturally suggests depth-first search, because DFS follows one path downward before trying another path.

## Key Insight

Instead of storing the whole path, we only need the remaining sum.

At each node, subtract the current node value from `targetSum`.

For example, suppose:

```python
targetSum = 22
```

At the root `5`, the remaining sum becomes:

```python
22 - 5 = 17
```

At node `4`, it becomes:

```python
17 - 4 = 13
```

At node `11`, it becomes:

```python
13 - 11 = 2
```

At leaf node `2`, the remaining sum becomes `0`.

So a valid path exists.

The important check happens only at a leaf. A partial path that sums to the target before reaching a leaf does not count.

## Algorithm

If `root` is `None`, return `False`.

Otherwise:

1. If the current node is a leaf, check whether its value equals `targetSum`.
2. Subtract the current node's value from `targetSum`.
3. Recursively check the left subtree.
4. Recursively check the right subtree.
5. Return `True` if either subtree has a valid path.

The recursive rule is:

```python
hasPathSum(node.left, targetSum - node.val)
or
hasPathSum(node.right, targetSum - node.val)
```

## Correctness

The algorithm explores every root-to-leaf path.

At each recursive call, `targetSum` represents the sum still needed from the current node down to a leaf.

If the current node is `None`, there is no path, so returning `False` is correct.

If the current node is a leaf, the current path is complete. The path is valid exactly when the leaf value equals the remaining target. Therefore, the algorithm returns `True` exactly for a leaf that completes a valid root-to-leaf sum.

If the current node is not a leaf, any valid path must continue through either the left child or the right child. After subtracting the current node value, the recursive calls check both possible continuations. If either side returns `True`, a valid path exists.

Therefore, the algorithm returns `True` exactly when the tree contains at least one root-to-leaf path whose values sum to `targetSum`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | In the worst case, every node is visited once |
| Space | `O(h)` | The recursion stack follows one root-to-leaf path |

Here, `n` is the number of nodes and `h` is the height of the tree.

For a balanced tree, `h = O(log n)`.

For a skewed tree, `h = O(n)`.

## 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False

        if root.left is None and root.right is None:
            return root.val == targetSum

        remaining = targetSum - root.val

        return (
            self.hasPathSum(root.left, remaining)
            or self.hasPathSum(root.right, remaining)
        )
```

## Code Explanation

The empty tree has no valid path:

```python
if root is None:
    return False
```

Check whether the current node is a leaf:

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

If it is a leaf, the path ends here. The path is valid only when the leaf value equals the remaining target:

```python
return root.val == targetSum
```

For a non-leaf node, subtract the current value:

```python
remaining = targetSum - root.val
```

Then check both subtrees:

```python
return (
    self.hasPathSum(root.left, remaining)
    or self.hasPathSum(root.right, remaining)
)
```

The `or` means one valid path is enough.

## 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False

        if root.left is None and root.right is None:
            return root.val == targetSum

        remaining = targetSum - root.val

        return (
            self.hasPathSum(root.left, remaining)
            or self.hasPathSum(root.right, remaining)
        )

def run_tests():
    s = Solution()

    root1 = TreeNode(
        5,
        TreeNode(
            4,
            TreeNode(11, TreeNode(7), TreeNode(2)),
            None,
        ),
        TreeNode(
            8,
            TreeNode(13),
            TreeNode(4, None, TreeNode(1)),
        ),
    )
    assert s.hasPathSum(root1, 22) is True

    root2 = TreeNode(1, TreeNode(2), TreeNode(3))
    assert s.hasPathSum(root2, 5) is False

    root3 = None
    assert s.hasPathSum(root3, 0) is False

    root4 = TreeNode(1)
    assert s.hasPathSum(root4, 1) is True
    assert s.hasPathSum(root4, 0) is False

    root5 = TreeNode(1, TreeNode(2), None)
    assert s.hasPathSum(root5, 1) is False
    assert s.hasPathSum(root5, 3) is True

    root6 = TreeNode(-2, None, TreeNode(-3))
    assert s.hasPathSum(root6, -5) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard tree with target `22` | Confirms a valid path is found |
| `[1,2,3]`, target `5` | Confirms invalid sums return `False` |
| Empty tree | Confirms no path exists |
| Single node | Confirms root can also be a leaf |
| Partial path sum equals target | Confirms path must end at a leaf |
| Negative values | Confirms subtraction works with negative numbers |