> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/binary_tree/vertical-order-traverse.md).

# Vertical Order Traverse

## 314. Binary Tree Vertical Order Traversal

```python
# 使用一個min_idx紀錄最小的idx
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
    record = defaultdict(list)
    min_idx = 0
    q = [(root, 0)]
    
    while q:
        node, idx = q.pop(0)
        if not node: continue
        min_idx = min(min_idx, idx)
        record[idx].append(node.val)
        q.append((node.left, idx-1))
        q.append((node.right, idx+1))
    
    ans = []
    
    for idx in sorted(record):
        ans.append(record[idx])
    
    return ans
```

## 987. Vertical Order Traversal of a Binary Tree

與上題不同的是，same position將按照increasing order 排列，需要紀錄x, y position的資料

```python
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
    position = defaultdict(lambda: defaultdict(list))
    q = [(root, 0, 0)]
    
    while q:
        node, x, y = q.pop(0)
        if not node: continue
        position[x][y].append(node.val)
        q.append((node.left, x-1, y+1))
        q.append((node.right, x+1, y+1))
    
    ans = []
    
    for x in sorted(position):
        container = []
        for y in sorted(position[x]):
            container += sorted(position[x][y])
        ans.append(container)
    
    return ans
```