# LeetCode 257: Binary Tree Paths

## Problem Restatement

We are given the root of a binary tree.

We need to return all paths from the root to every leaf node.

A leaf node is a node with no left child and no right child.

Each path must be returned as a string using `"->"` between node values.

For example, this path:

```text
1
 \
  2
   \
    5
```

becomes:

```python
"1->2->5"
```

The problem asks for all root-to-leaf paths in any order. The tree has between `1` and `100` nodes, and each node value is between `-100` and `100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root node of a binary tree |
| Output | List of root-to-leaf path strings |
| Leaf | A node with no children |
| Path format | Values joined by `"->"` |

Example function shape:

```python
def binaryTreePaths(root: Optional[TreeNode]) -> list[str]:
    ...
```

## Examples

Example 1:

```python
root = [1, 2, 3, None, 5]
```

Tree:

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

There are two root-to-leaf paths.

The first path is:

```python
"1->2->5"
```

The second path is:

```python
"1->3"
```

Answer:

```python
["1->2->5", "1->3"]
```

Example 2:

```python
root = [1]
```

The root itself is also a leaf.

Answer:

```python
["1"]
```

## First Thought: Traverse Every Path

A binary tree path starts at the root and moves down through child pointers.

So the natural approach is depth-first search.

While walking down the tree, we keep the current path.

When we reach a leaf, the current path is complete, so we convert it into a string and add it to the answer.

## Problem With Building Strings Too Early

One simple method is to pass a string into every recursive call.

For example:

```python
dfs(node.left, path + "->" + str(node.left.val))
```

This works, but it repeatedly creates new strings.

For small input this is fine. But a cleaner general technique is to keep a list of path values, then join the list only when we reach a leaf.

That gives a standard backtracking shape.

## Key Insight

At any node, the current path contains all values from the root to that node.

For example, in this tree:

```text
    1
   /
  2
   \
    5
```

when DFS reaches node `5`, the path list is:

```python
["1", "2", "5"]
```

Since `5` is a leaf, we convert it into:

```python
"1->2->5"
```

Then we backtrack by removing `5`, so the path can be reused for other branches.

## Algorithm

Use DFS with a mutable path list.

At each node:

1. Add the current node value to `path`.
2. If the node is a leaf:
   - Join `path` using `"->"`.
   - Add the joined string to `ans`.
3. Otherwise:
   - DFS into the left child.
   - DFS into the right child.
4. Remove the current node value from `path`.

The final pop is the backtracking step.

## Walkthrough

Use this tree:

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

Start at node `1`.

```python
path = ["1"]
```

Move left to node `2`.

```python
path = ["1", "2"]
```

Node `2` is not a leaf because it has a right child.

Move right to node `5`.

```python
path = ["1", "2", "5"]
```

Node `5` is a leaf.

Add:

```python
"1->2->5"
```

Backtrack to node `2`, then backtrack to node `1`.

Now move right to node `3`.

```python
path = ["1", "3"]
```

Node `3` is a leaf.

Add:

```python
"1->3"
```

The final answer is:

```python
["1->2->5", "1->3"]
```

## Correctness

The DFS visits every node reachable from the root.

During each recursive call, `path` contains exactly the node values on the current root-to-current-node path. This is true because we append the current node before exploring its children, and remove it after finishing that node.

When DFS reaches a leaf, the current path starts at the root and ends at that leaf. So joining the path produces a valid root-to-leaf path string.

Every root-to-leaf path is found because DFS explores both left and right children of every non-leaf node.

No invalid path is added because the algorithm appends to `ans` only when the current node has no children.

Therefore the algorithm returns exactly all root-to-leaf paths.

## Complexity

Let `n` be the number of nodes and `h` be the height of the tree.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * h)` | Each node is visited once, and each leaf path string can take up to `h` work to build |
| Space | `O(h)` | The recursion stack and current path store one root-to-current-node path |

The output itself also takes space proportional to the total length of all returned path strings.

## Implementation

```python
from typing import Optional, List

# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        ans = []
        path = []

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

            path.append(str(node.val))

            if node.left is None and node.right is None:
                ans.append("->".join(path))
            else:
                dfs(node.left)
                dfs(node.right)

            path.pop()

        dfs(root)
        return ans
```

## Code Explanation

We store completed path strings in:

```python
ans = []
```

We store the current root-to-node path in:

```python
path = []
```

The DFS ignores empty nodes:

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

When we enter a node, we add its value:

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

We store strings instead of integers because the final output uses string joining.

A node is a leaf when both children are missing:

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

At a leaf, the path is complete:

```python
ans.append("->".join(path))
```

For a non-leaf node, we continue searching:

```python
dfs(node.left)
dfs(node.right)
```

After finishing the current node, we remove it from the path:

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

This restores the path before returning to the parent.

## Testing

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

def normalize(paths: list[str]) -> list[str]:
    return sorted(paths)

def run_tests():
    s = Solution()

    root = TreeNode(
        1,
        TreeNode(2, None, TreeNode(5)),
        TreeNode(3),
    )
    assert normalize(s.binaryTreePaths(root)) == normalize(["1->2->5", "1->3"])

    root = TreeNode(1)
    assert s.binaryTreePaths(root) == ["1"]

    root = TreeNode(1, TreeNode(2), None)
    assert s.binaryTreePaths(root) == ["1->2"]

    root = TreeNode(1, None, TreeNode(3))
    assert s.binaryTreePaths(root) == ["1->3"]

    root = TreeNode(-1, TreeNode(-2), TreeNode(3))
    assert normalize(s.binaryTreePaths(root)) == normalize(["-1->-2", "-1->3"])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Two root-to-leaf paths | Standard example |
| Single node | Root is also a leaf |
| Only left child | Handles one-sided tree |
| Only right child | Handles missing left subtree |
| Negative values | Confirms string conversion handles signs |