# 6ms, BFS solution.

• Basically, the idea is: traverse all nodes using bfs, keep track of all nodes vertical order using map, which is, left node is 1 less than root and right node is 1 more than root.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
Map<Integer, List<Integer>> map = new HashMap<>();
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
} else {
queue.offer(new Item(root, 0));
Item dummy = new Item(null, Integer.MAX_VALUE);
queue.offer(dummy);
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
while (!queue.isEmpty()) {
Item it = queue.poll();
if (queue.isEmpty() && it == dummy) {
break;
} else if (it == dummy) {
queue.offer(dummy);
} else {
int order = it.order;
min = Math.min(min, order);
max = Math.max(max, order);
if (!map.containsKey(order)) {
map.put(order, new ArrayList<>());
}
if (it.node.left != null) {
queue.offer(new Item(it.node.left, it.order - 1));
}
if (it.node.right != null) {
queue.offer(new Item(it.node.right, it.order + 1));
}
}
}
for (int i = min;i <= max; i++) {
}
return result;
}
}

class Item {
TreeNode node;
int order;
public Item(TreeNode n, int o) {
this.node = n;
this.order = o;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.