> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0314-binary-tree-vertical-order-traversal.md).

# 0314. Binary Tree Vertical Order Traversal

<https://leetcode.com/problems/binary-tree-vertical-order-traversal>

## Description

Given the `root` of a binary tree, return ***the vertical order traversal** of its nodes' values*. (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**.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/28/vtree1.jpg)

```
**Input:** root = [3,9,20,null,null,15,7]
**Output:** [[9],[3,15],[20],[7]]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/01/28/vtree2-1.jpg)

```
**Input:** root = [3,9,8,4,0,1,7]
**Output:** [[4],[9],[3,0,1],[8],[7]]
```

**Example 3:**

![](https://assets.leetcode.com/uploads/2021/01/28/vtree2.jpg)

```
**Input:** root = [3,9,8,4,0,1,7,null,null,null,2,5]
**Output:** [[4],[9,5],[3,0,1],[8,2],[7]]
```

**Example 4:**

```
**Input:** root = []
**Output:** []
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 100]`.
* `-100 <= Node.val <= 100`

## ac

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        // edge case
        if (root == null) return res;

        TreeMap<Integer, List<Integer>> tm = new TreeMap<>();

        // BFS
        Queue<TreeNode> q = new LinkedList<>();
        tm.put(0, new ArrayList<Integer>());
        tm.get(0).add(root.val);
        root.val = 0;
        q.offer(root);

        while (!q.isEmpty()) {
            TreeNode curr = q.poll();

            // left
            if (curr.left != null) {
                if (!tm.containsKey(curr.val-1)) tm.put(curr.val-1, new ArrayList<Integer>());
                tm.get(curr.val-1).add(curr.left.val);
                curr.left.val = curr.val-1;
                q.offer(curr.left);
            }
            // right
            if (curr.right != null) {
                if (!tm.containsKey(curr.val+1)) tm.put(curr.val+1, new ArrayList<Integer>());
                tm.get(curr.val+1).add(curr.right.val);
                curr.right.val = curr.val+1;
                q.offer(curr.right);
            }

        }

        for (int i : tm.keySet()) {
            res.add(tm.get(i));
        }

        return res;
    }
}
```

```
 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2 
```

```
 [ [4], [9,5], [3,0,1], [8,2], [7] ] 
```