# LeetCode 666: Path Sum IV

## Problem Restatement

We are given an array `nums`.

Each integer in `nums` has exactly three digits and represents one node in a binary tree.

For a number `DPV`:

| Digit | Meaning |
|---|---|
| `D` | Depth of the node |
| `P` | Position of the node within that depth |
| `V` | Value of the node |

Depth and position are 1-based.

The tree depth is less than `5`, so valid depths are from `1` to `4`.

We need to return the sum of all root-to-leaf path sums.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of three-digit integers |
| Output | Sum of all root-to-leaf path sums |
| Hundreds digit | Node depth |
| Tens digit | Node position |
| Units digit | Node value |
| Tree guarantee | The array represents a valid connected binary tree |

Example function shape:

```python
def pathSum(nums: list[int]) -> int:
    ...
```

## Examples

Consider:

```python
nums = [113, 215, 221]
```

Decode each number:

| Number | Depth | Position | Value |
|---|---|---|---|
| `113` | `1` | `1` | `3` |
| `215` | `2` | `1` | `5` |
| `221` | `2` | `2` | `1` |

The tree is:

```text
    3
   / \
  5   1
```

The root-to-leaf path sums are:

```text
3 + 5 = 8
3 + 1 = 4
```

So the answer is:

```text
8 + 4 = 12
```

Another example:

```python
nums = [113, 221]
```

The tree is:

```text
  3
   \
    1
```

There is one root-to-leaf path:

```text
3 + 1 = 4
```

So the answer is:

```python
4
```

## First Thought: Build Tree Nodes

One direct solution is to create normal `TreeNode` objects.

For each encoded number, we decode its depth, position, and value. Then we connect each node to its parent.

This works, but it is more work than necessary.

The input already gives us enough information to traverse the tree directly.

We only need a way to quickly ask:

```text
Does this node exist?
```

and:

```text
What is its value?
```

A hash map is enough.

## Key Insight

A node can be identified by its depth and position.

For a node at:

```text
depth = d
position = p
```

its children are:

| Child | Depth | Position |
|---|---|---|
| Left child | `d + 1` | `2 * p - 1` |
| Right child | `d + 1` | `2 * p` |

So we store:

```python
(depth, position) -> value
```

Then we run DFS from the root:

```python
(1, 1)
```

During DFS, we keep the current path sum.

When we reach a leaf, we add that path sum to the answer.

## Leaf Detection

A node is a leaf if it has no left child and no right child.

For node `(d, p)`, the possible children are:

```python
(d + 1, 2 * p - 1)
(d + 1, 2 * p)
```

If neither key exists in the map, the node is a leaf.

## Algorithm

1. Create an empty hash map called `tree`.
2. For every encoded number:
   - Extract depth.
   - Extract position.
   - Extract value.
   - Store the value using `(depth, position)` as the key.
3. Run DFS from `(1, 1)` with path sum `0`.
4. At each node:
   - Add the node value to the path sum.
   - Check whether it has children.
   - If it has no children, add the path sum to the answer.
   - Otherwise, recursively visit existing children.
5. Return the answer.

## Correctness

Each encoded integer uniquely identifies one node by its depth and position. The hash map stores exactly these nodes and their values.

For any node `(d, p)`, the full-tree position rule gives its left child as `(d + 1, 2p - 1)` and its right child as `(d + 1, 2p)`. Therefore, checking these two keys correctly determines which children exist.

The DFS starts at the root `(1, 1)` and follows only existing child positions. Since the input represents a valid connected binary tree, this visits every node reachable from the root.

The path sum passed through DFS is the sum of node values from the root to the current node. When a leaf is reached, this path is a complete root-to-leaf path, so adding the path sum to the answer is correct.

Every root-to-leaf path ends at exactly one leaf, and the DFS visits every leaf once. Therefore, the algorithm adds every root-to-leaf path sum exactly once and returns the required total.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each encoded node is processed once |
| Space | `O(n)` | The hash map stores all nodes |

The recursion depth is at most `4`, because the problem limits tree depth to less than `5`.

## Implementation

```python
from typing import List

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        tree = {}

        for num in nums:
            depth = num // 100
            position = (num // 10) % 10
            value = num % 10

            tree[(depth, position)] = value

        answer = 0

        def dfs(depth: int, position: int, path_sum: int) -> None:
            nonlocal answer

            if (depth, position) not in tree:
                return

            path_sum += tree[(depth, position)]

            left = (depth + 1, 2 * position - 1)
            right = (depth + 1, 2 * position)

            if left not in tree and right not in tree:
                answer += path_sum
                return

            dfs(left[0], left[1], path_sum)
            dfs(right[0], right[1], path_sum)

        dfs(1, 1, 0)

        return answer
```

## Code Explanation

We decode every three-digit number:

```python
depth = num // 100
position = (num // 10) % 10
value = num % 10
```

For example, `215` becomes:

| Field | Value |
|---|---|
| `depth` | `2` |
| `position` | `1` |
| `value` | `5` |

We store the node in a map:

```python
tree[(depth, position)] = value
```

The DFS receives the current logical node location:

```python
def dfs(depth: int, position: int, path_sum: int) -> None:
```

If the node does not exist, we stop:

```python
if (depth, position) not in tree:
    return
```

Otherwise, we add the current node value:

```python
path_sum += tree[(depth, position)]
```

Then we compute both child positions:

```python
left = (depth + 1, 2 * position - 1)
right = (depth + 1, 2 * position)
```

If neither child exists, the current node is a leaf:

```python
if left not in tree and right not in tree:
    answer += path_sum
    return
```

Otherwise, we continue to both children:

```python
dfs(left[0], left[1], path_sum)
dfs(right[0], right[1], path_sum)
```

The missing child check inside DFS safely ignores nonexistent children.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.pathSum([113, 215, 221]) == 12
    assert s.pathSum([113, 221]) == 4

    # Tree:
    #     1
    #    / \
    #   2   3
    #  /
    # 4
    assert s.pathSum([111, 212, 223, 314]) == 8

    # Single root.
    assert s.pathSum([117]) == 7

    # Tree:
    #       5
    #      /
    #     0
    #      \
    #       9
    assert s.pathSum([115, 210, 329]) == 14

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[113,215,221]` | Standard two-leaf example |
| `[113,221]` | Root with only right child |
| Deeper left path | Checks recursive accumulation |
| Single root | Root is also a leaf |
| Zero-valued node | Confirms value `0` is handled correctly |