# LeetCode 314: Binary Tree Vertical Order Traversal

## Problem Restatement

We are given the root of a binary tree.

Return the vertical order traversal of the tree's node values.

Vertical order means:

1. Group nodes by column.
2. Output columns from left to right.
3. Inside each column, output nodes from top to bottom.
4. If two nodes have the same row and column, output the left node before the right node.

The root starts at column `0`.

For any node:

| Child | Column |
|---|---:|
| Left child | `col - 1` |
| Right child | `col + 1` |

The official statement asks for vertical order traversal from top to bottom, column by column, with left-to-right ordering when two nodes share the same row and column.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | List of columns, each column containing node values |
| Column order | Leftmost column to rightmost column |
| Inside one column | Top to bottom |
| Tie rule | Same row and column keeps left-to-right order |

Function shape:

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

## Examples

Example 1:

```text
        3
       / \
      9   20
         /  \
        15   7
```

Column assignment:

| Node | Column |
|---:|---:|
| `9` | `-1` |
| `3` | `0` |
| `15` | `0` |
| `20` | `1` |
| `7` | `2` |

Output:

```python
[[9], [3, 15], [20], [7]]
```

Example 2:

```text
        3
       / \
      9   8
     / \ / \
    4  0 1  7
```

Columns:

| Column | Values |
|---:|---|
| `-2` | `[4]` |
| `-1` | `[9]` |
| `0` | `[3, 0, 1]` |
| `1` | `[8]` |
| `2` | `[7]` |

Output:

```python
[[4], [9], [3, 0, 1], [8], [7]]
```

Notice column `0`.

Nodes `0` and `1` are on the same row and same column. Since `0` comes from the left side and `1` comes from the right side, `0` appears first.

## First Thought: DFS With Sorting

One possible solution is:

1. Traverse the tree.
2. Record each node as `(column, row, order, value)`.
3. Sort by column, then row, then order.
4. Group by column.

This works, but sorting adds extra complexity.

There is a cleaner approach because the required order inside each column is top to bottom, and ties follow left-to-right tree order.

That is exactly what BFS gives us.

## Key Insight

Use BFS level-order traversal.

BFS visits nodes by row from top to bottom.

If we push the left child before the right child, then nodes on the same row are visited from left to right.

So if we append each visited node into its column bucket during BFS, each bucket naturally has the correct order.

We only need to track the column index of each node.

## Algorithm

If `root` is `None`, return an empty list.

Otherwise:

1. Create a dictionary:
   ```python id="6vmqc4"
   column_map = defaultdict(list)
   ```
2. Create a queue containing:
   ```python id="53b0ym"
   (root, 0)
   ```
3. Track the smallest and largest column seen.
4. While the queue is not empty:
   - Pop `(node, col)`.
   - Append `node.val` to `column_map[col]`.
   - If `node.left` exists, push `(node.left, col - 1)`.
   - If `node.right` exists, push `(node.right, col + 1)`.
5. Return buckets from `min_col` through `max_col`.

## Correctness

BFS processes nodes level by level. Therefore, when a value is appended to a column bucket, all nodes above it have already been processed.

Within the same level, BFS processes nodes from left to right because we enqueue the left child before the right child for every node. Therefore, if two nodes share the same row and column, the left-side node is appended first.

Each node is assigned the correct column because the root starts at column `0`, every left edge subtracts `1`, and every right edge adds `1`.

The dictionary groups exactly the nodes with equal column indices. Returning columns from `min_col` to `max_col` outputs them from left to right.

Therefore, the algorithm returns the required vertical order traversal.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(n)` | Queue and column map store up to `n` nodes |

`n` is the number of nodes in the tree.

## Implementation

```python
from collections import defaultdict, deque
from typing import Optional

class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def verticalOrder(
        self,
        root: Optional[TreeNode],
    ) -> list[list[int]]:

        if root is None:
            return []

        column_map = defaultdict(list)
        queue = deque([(root, 0)])

        min_col = 0
        max_col = 0

        while queue:
            node, col = queue.popleft()

            column_map[col].append(node.val)

            min_col = min(min_col, col)
            max_col = max(max_col, col)

            if node.left:
                queue.append((node.left, col - 1))

            if node.right:
                queue.append((node.right, col + 1))

        return [
            column_map[col]
            for col in range(min_col, max_col + 1)
        ]
```

## Code Explanation

We handle the empty tree first.

```python
if root is None:
    return []
```

The column map stores one list per vertical column.

```python
column_map = defaultdict(list)
```

The queue stores each node with its column.

```python
queue = deque([(root, 0)])
```

The root is at column `0`.

We also track the leftmost and rightmost columns.

```python
min_col = 0
max_col = 0
```

During BFS:

```python
node, col = queue.popleft()
```

Append the node value to its column.

```python
column_map[col].append(node.val)
```

Update boundaries.

```python
min_col = min(min_col, col)
max_col = max(max_col, col)
```

The left child goes one column left.

```python
if node.left:
    queue.append((node.left, col - 1))
```

The right child goes one column right.

```python
if node.right:
    queue.append((node.right, col + 1))
```

Finally, build the answer from leftmost column to rightmost column.

```python
return [
    column_map[col]
    for col in range(min_col, max_col + 1)
]
```

## Testing

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

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(
            20,
            TreeNode(15),
            TreeNode(7),
        ),
    )

    assert s.verticalOrder(root1) == [
        [9],
        [3, 15],
        [20],
        [7],
    ]

    root2 = TreeNode(
        3,
        TreeNode(
            9,
            TreeNode(4),
            TreeNode(0),
        ),
        TreeNode(
            8,
            TreeNode(1),
            TreeNode(7),
        ),
    )

    assert s.verticalOrder(root2) == [
        [4],
        [9],
        [3, 0, 1],
        [8],
        [7],
    ]

    assert s.verticalOrder(None) == []

    single = TreeNode(1)
    assert s.verticalOrder(single) == [[1]]

    left_chain = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(3),
        ),
    )
    assert s.verticalOrder(left_chain) == [[3], [2], [1]]

    right_chain = TreeNode(
        1,
        None,
        TreeNode(
            2,
            None,
            TreeNode(3),
        ),
    )
    assert s.verticalOrder(right_chain) == [[1], [2], [3]]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks normal vertical grouping |
| Same row and column tie | Confirms left-to-right BFS order |
| Empty tree | Checks null input |
| Single node | Smallest non-empty tree |
| Left chain | Multiple negative columns |
| Right chain | Multiple positive columns |