# LeetCode 987: Vertical Order Traversal of a Binary Tree

## Problem Restatement

We are given the root of a binary tree.

Each node has a coordinate:

| Node | Position |
|---|---|
| Root | `(row = 0, col = 0)` |
| Left child | `(row + 1, col - 1)` |
| Right child | `(row + 1, col + 1)` |

We need to return the vertical order traversal of the tree.

That means:

1. Visit columns from left to right.
2. Inside each column, visit nodes from top to bottom.
3. If multiple nodes have the same row and column, sort them by value.

The number of nodes is in the range `[1, 1000]`, and node values are in the range `[0, 1000]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a binary tree |
| Output | List of columns, each containing node values |
| Column order | Smaller column index first |
| Row order | Smaller row index first |
| Tie rule | Same row and same column: smaller node value first |

Function shape:

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

## Examples

Example 1:

```python
root = [3, 9, 20, None, None, 15, 7]
```

Tree:

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

Coordinates:

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

Group by column:

| Column | Values |
|---:|---|
| `-1` | `[9]` |
| `0` | `[3, 15]` |
| `1` | `[20]` |
| `2` | `[7]` |

Answer:

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

Example 2:

```python
root = [1, 2, 3, 4, 5, 6, 7]
```

Tree:

```text
        1
      /   \
     2     3
    / \   / \
   4   5 6   7
```

Coordinates:

| Value | Row | Column |
|---:|---:|---:|
| `1` | `0` | `0` |
| `2` | `1` | `-1` |
| `3` | `1` | `1` |
| `4` | `2` | `-2` |
| `5` | `2` | `0` |
| `6` | `2` | `0` |
| `7` | `2` | `2` |

At coordinate `(2, 0)`, both `5` and `6` appear. Since they share the same row and column, they are sorted by value.

Answer:

```python
[[4], [2], [1, 5, 6], [3], [7]]
```

## First Thought: Traverse and Group by Column

A natural idea is to do DFS or BFS and put every node into a dictionary by column.

For example:

```python
column -> list of node values
```

But this is not enough.

Inside a column, nodes must be ordered by row. Also, if two nodes have the same row and column, they must be ordered by value.

So we need to remember three pieces of information for every node:

```python
column, row, value
```

## Key Insight

If we collect every node as a tuple:

```python
(column, row, value)
```

then Python's default tuple sorting gives exactly the order we need:

1. Sort by column.
2. If columns tie, sort by row.
3. If rows tie, sort by value.

After sorting, all nodes from the same column are next to each other. We can scan the sorted list and group values by column.

## Algorithm

Use DFS.

For each node:

1. Record `(column, row, node.val)`.
2. Visit the left child with `(row + 1, column - 1)`.
3. Visit the right child with `(row + 1, column + 1)`.

After DFS:

1. Sort all recorded tuples.
2. Scan the sorted tuples.
3. Start a new group whenever the column changes.
4. Append node values to the current column group.
5. Return all groups.

## Correctness

The DFS visits every node exactly once and records its correct coordinate. The root starts at `(0, 0)`. For every node at `(row, column)`, the algorithm assigns the left child to `(row + 1, column - 1)` and the right child to `(row + 1, column + 1)`, matching the coordinate definition.

After all nodes are recorded, sorting tuples `(column, row, value)` orders nodes first by column from left to right, then by row from top to bottom, and then by value for nodes at the same position.

The final scan groups consecutive tuples with the same column. Since sorting places all equal-column tuples together and already orders them correctly within the column, each group is exactly one vertical column in the required order.

Therefore, the algorithm returns the correct vertical traversal.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | We sort `n` recorded nodes |
| Space | `O(n)` | We store all node tuples and use recursion stack |

The recursion stack can be `O(h)`, where `h` is the tree height, but the tuple list dominates in the general complexity.

## Implementation

```python
# 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 verticalTraversal(self, root: Optional[TreeNode]) -> list[list[int]]:
        nodes = []

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

            nodes.append((col, row, node.val))

            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        nodes.sort()

        answer = []
        current_col = None

        for col, row, value in nodes:
            if col != current_col:
                answer.append([])
                current_col = col

            answer[-1].append(value)

        return answer
```

## Code Explanation

We collect all positioned nodes here:

```python
nodes = []
```

The DFS receives both coordinates:

```python
def dfs(node: Optional[TreeNode], row: int, col: int) -> None:
```

If the node is missing, there is nothing to record:

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

For a real node, record:

```python
nodes.append((col, row, node.val))
```

The order is important. We store column first because the final output is grouped by column.

Then visit children with their coordinate changes:

```python
dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)
```

After collecting all nodes, sort them:

```python
nodes.sort()
```

This sorts by column, then row, then value.

Finally, group values by column:

```python
for col, row, value in nodes:
    if col != current_col:
        answer.append([])
        current_col = col

    answer[-1].append(value)
```

## Testing

```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

def run_tests():
    s = Solution()

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

    root2 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7)),
    )
    assert s.verticalTraversal(root2) == [[4], [2], [1, 5, 6], [3], [7]]

    root3 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(6)),
        TreeNode(3, TreeNode(5), TreeNode(7)),
    )
    assert s.verticalTraversal(root3) == [[4], [2], [1, 5, 6], [3], [7]]

    root4 = TreeNode(1)
    assert s.verticalTraversal(root4) == [[1]]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[3,9,20,null,null,15,7]` | `[[9],[3,15],[20],[7]]` | Standard vertical traversal |
| `[1,2,3,4,5,6,7]` | `[[4],[2],[1,5,6],[3],[7]]` | Tie by same row and column |
| Swapped middle values | `[[4],[2],[1,5,6],[3],[7]]` | Same-position nodes sorted by value |
| `[1]` | `[[1]]` | Single-node tree |