> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/bfs/binary-tree-vertical-order-traversal.md).

# Binary Tree Vertical Order Traversal

## Question ([LC.314](https://leetcode.com/problems/binary-tree-vertical-order-traversal/#/description))

> Given a binary tree, return the vertical order traversal of its nodes' values.

## Example

```
I: root = [3,9,20,null,null,15,7]
O: [[9], [3, 15], [20], [7]]

I: root = [3,9,8,4,0,1,7,null,null,null,2,5]
O: [[4], [9,5], [3,0,1], [8,2], [7]]
```

## Analysis

The key of unlocking this question is to understand the definition of vertical order. 

> i.e. from top to bottom, column by column
>
> if two nodes are in the same row and column, the order should be from **left to right**.

There are two conditions in this ordering, rows and columns. I have missed the rows part when I first read this question. 

For example, `[3,9,8,4,0,1,7,null,null,null,2,5]` has the following diagram. 

![Vertical order binary tree](/files/-MWNBxgvSSAchKd503hE)

Which can be represented in a matrix like this 

| row/col | -2 | -1 | 0   | 1 | 2 |
| ------- | -- | -- | --- | - | - |
| 0       |    |    | 3   |   |   |
| 1       |    | 9  |     | 8 |   |
| 2       | 4  |    | 0,1 |   | 7 |
| 3       |    | 5  |     | 2 |   |

A corner case without row key with DFS is `[8, 2]` will be `[2, 8]`. BFS gets row key sort of for free.  

## DFS Code 

```python
class Solution:
    
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        
        results: List[List[int]] = []
        
        if root is None:
            return results 
        
        node_dict: Dict[TreeNode, Tuple[int, int]] = {}
        
        self.preorder(root, node_dict, 0, 0)
        
        # group by col score 
        score_dict: Dict[int, List[Tuple[int, int]]] = defaultdict(list)
        
        for node in node_dict:
            col_score = node_dict[node][0]
            row_score = node_dict[node][1]
            score_dict[col_score].append((node.val, row_score))
        
        sorted_scores = sorted(score_dict)
        
        for score in sorted_scores:
            # sort by row score 
            vertical_order = [
                ele[0] for ele in sorted(score_dict[score], key=lambda t: t[1])
            ]
            results.append(
                vertical_order
            )
        
        return results
     
        
    def preorder(
        self, 
        node: TreeNode, 
        node_dict: Dict[TreeNode, Tuple[int, int]], 
        col_score: int,
        row_score: int
    ) -> None:
        
        if node is None:
            return 
        
        # visit 
        node_dict[node] = (col_score, row_score)
        
        # go left 
        self.preorder(node.left, node_dict, col_score - 1, row_score + 1) 
        
        # go right 
        self.preorder(node.right, node_dict, col_score + 1, row_score + 1)
    
```

time `O(nlogn)`

space `O(n)` 

## BFS Code 

```python
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
    
    results: List[List[int]] = []
    
    if root is None:
        return results 
    
    queue: Deque[Tuple[TreeNode, int]] = deque()
    queue.append((root, 0))
    col_map: Dict[int, List[int]] = defaultdict(list)
    
    while len(queue) > 0:
        cur_tuple = queue.popleft()
        cur_node = cur_tuple[0]
        cur_col = cur_tuple[1]
        col_map[cur_col].append(cur_node.val)
        
        if cur_node.left:
            queue.append((cur_node.left, cur_col - 1))
        
        if cur_node.right:
            queue.append((cur_node.right, cur_col + 1))
    
    sorted_keys = sorted(col_map)
    
    for key in sorted_keys:
        results.append(col_map[key])
    
    return results 
```

time `O(nlogn)`

space `O(n)`