# LeetCode 144: Binary Tree Preorder Traversal

## Problem Restatement

We are given the root of a binary tree.

Return the preorder traversal of its node values.

Preorder traversal visits nodes in this order:

```text
root -> left subtree -> right subtree
```

The tree may be empty. In that case, return an empty list. LeetCode also includes a follow-up asking for an iterative solution.

## Examples

Example 1:

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

Preorder traversal:

```text
visit 1
go right to 2
visit 2
go left to 3
visit 3
```

Output:

```python
[1, 2, 3]
```

Example 2:

```python
root = []
```

Output:

```python
[]
```

Example 3:

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

Output:

```python
[1]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root: Optional[TreeNode]` |
| Output | `list[int]` |
| Traversal order | Root, left subtree, right subtree |
| Empty tree | Return `[]` |

Function shape:

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

## Core Idea

Preorder traversal is a depth-first traversal.

At each node, we do three things:

1. Visit the current node.
2. Traverse the left subtree.
3. Traverse the right subtree.

So the recursive structure follows the traversal definition directly:

```python
visit(node)
preorder(node.left)
preorder(node.right)
```

## Recursive Algorithm

Create an empty result list.

Define a helper function:

```python
dfs(node)
```

For each node:

1. If `node` is `None`, return.
2. Append `node.val` to the result.
3. Recursively traverse `node.left`.
4. Recursively traverse `node.right`.

Return the result list.

## Correctness

For any non-empty subtree, preorder traversal requires visiting the subtree root before its children.

The algorithm first appends the current node value, so it visits the root first.

Then it recursively applies the same rule to the left subtree, which returns all left-subtree values in preorder.

After that, it recursively applies the same rule to the right subtree, which returns all right-subtree values in preorder.

Therefore, every subtree is processed in root-left-right order. Applying this to the original root gives the preorder traversal of the whole tree.

If the tree is empty, the helper does nothing and the result remains empty, so the algorithm returns `[]`.

## Complexity

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(h)` | Recursion stack follows one root-to-leaf path |

In the worst case, a skewed tree has height `n`.

## Recursive 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 preorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        result = []

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

            result.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return result
```

## Code Explanation

The result list stores visited values:

```python
result = []
```

The helper receives the current node:

```python
def dfs(node: Optional[TreeNode]) -> None:
```

The base case stops at missing children:

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

Preorder visits the root first:

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

Then it visits the left subtree:

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

Then it visits the right subtree:

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

Finally, the main function returns the collected values:

```python
return result
```

## Iterative Implementation

The follow-up asks for an iterative solution.

Use a stack.

Because a stack is last-in-first-out, push the right child before the left child. That way, the left child is processed first.

```python
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            if node.right is not None:
                stack.append(node.right)

            if node.left is not None:
                stack.append(node.left)

        return result
```

## Iterative Code Explanation

Start with the root on the stack:

```python
stack = [root]
```

While there is a node to process:

```python
node = stack.pop()
```

visit it:

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

Push the right child first:

```python
if node.right is not None:
    stack.append(node.right)
```

Then push the left child:

```python
if node.left is not None:
    stack.append(node.left)
```

Since the left child is on top of the stack, it is processed before the right child.

## Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    assert s.preorderTraversal(root) == [1, 2, 3]

    assert s.preorderTraversal(None) == []

    root = TreeNode(1)
    assert s.preorderTraversal(root) == [1]

    root = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )
    assert s.preorderTraversal(root) == [1, 2, 4, 5, 3]

    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert s.preorderTraversal(root) == [1, 2, 3]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1 -> right 2 -> left 3` | Standard LeetCode example shape |
| Empty tree | Returns empty list |
| Single node | Root-only traversal |
| Full mixed tree | Confirms root-left-right order |
| Left-skewed tree | Confirms recursive descent order |