# LeetCode 1022: Sum of Root To Leaf Binary Numbers

## Problem Restatement

We are given the root of a binary tree where each node has value `0` or `1`.

Each root-to-leaf path represents a binary number.

We need to return the sum of all these binary numbers.

The official constraints state that the number of nodes is in `[1, 1000]`, `Node.val` is `0` or `1`, and the answer fits in a 32-bit integer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree with `0/1` node values |
| Output | Sum of all root-to-leaf binary numbers |

Function shape:

```python
def sumRootToLeaf(root: Optional[TreeNode]) -> int:
    ...
```

## Examples

Example 1:

```python
root = [1, 0, 1, 0, 1, 0, 1]
```

The tree looks like:

```
      1
     / \
    0   1
   / \ / \
  0  1 0  1
```

Paths and their binary values:

| Path | Binary | Decimal |
|---|---|---:|
| 1 → 0 → 0 | `100` | 4 |
| 1 → 0 → 1 | `101` | 5 |
| 1 → 1 → 0 | `110` | 6 |
| 1 → 1 → 1 | `111` | 7 |

Sum = `4 + 5 + 6 + 7 = 22`.

Answer:

```python
22
```

## Key Insight

As we walk from root to a leaf, we accumulate the binary number bit by bit.

When we move to a child, the current number shifts left (multiply by `2`) and the child's value is appended.

When we reach a leaf, the accumulated value is one of the binary numbers to sum.

## Algorithm

Define a recursive DFS function `dfs(node, current)`:

1. If `node` is `None`, return `0`.
2. `current = current * 2 + node.val`.
3. If `node` is a leaf, return `current`.
4. Return `dfs(node.left, current) + dfs(node.right, current)`.

## Correctness

At each node, `current` holds the binary number formed by the path from the root to that node.

Multiplying by `2` shifts the binary digits left, and adding `node.val` appends the new bit.

At a leaf, the accumulated value is the complete binary number for that root-to-leaf path.

## Edge Cases

- A missing child should not contribute a fake value to min/max or path computations.
- Leaf nodes often define the base case; verify the behavior on a single-node tree.
- When passing state down the tree, update it before visiting children that depend on the current node.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | Recursion stack of tree height |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```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 sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current: int) -> int:
            if node is None:
                return 0
            current = current * 2 + node.val
            if node.left is None and node.right is None:
                return current
            return dfs(node.left, current) + dfs(node.right, current)

        return dfs(root, 0)
```

## Code Explanation

Accumulate the binary value as we descend:

```python
current = current * 2 + node.val
```

Return the accumulated value when reaching a leaf:

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

Otherwise, sum the results from left and right subtrees:

```python
return dfs(node.left, current) + dfs(node.right, current)
```

## Testing

```python
def run_tests():
    root1 = TreeNode(1,
        TreeNode(0, TreeNode(0), TreeNode(1)),
        TreeNode(1, TreeNode(0), TreeNode(1))
    )
    s = Solution()
    assert s.sumRootToLeaf(root1) == 22

    root2 = TreeNode(0)
    assert s.sumRootToLeaf(root2) == 0

    root3 = TreeNode(1, TreeNode(1))
    assert s.sumRootToLeaf(root3) == 3

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Full binary tree | `22` | `4+5+6+7` |
| Single node `0` | `0` | `0` in binary |
| `1 → 1` | `3` | `11` in binary |