# 5ms Java Clean Solution

• The following solution takes `5ms`.

• BFS, put `node`, `col` into queue at the same time
• Every left child access `col - 1` while right child `col + 1`
• This maps `node` into different `col` buckets
• Get `col` boundary `min` and `max` on the fly
• Retrieve `result` from `cols`

Note that `TreeMap` version takes `9ms`.

Here is an example of `[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]`. Notice that every child access changes one column bucket id. So `12` actually goes ahead of `11`.

``````public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}

Map<Integer, ArrayList<Integer>> map = new HashMap<>();

int min = 0;
int max = 0;

while (!q.isEmpty()) {
TreeNode node = q.poll();
int col = cols.poll();

if (!map.containsKey(col)) {
map.put(col, new ArrayList<Integer>());
}

if (node.left != null) {
min = Math.min(min, col - 1);
}

if (node.right != null) {
max = Math.max(max, col + 1);
}
}

for (int i = min; i <= max; i++) {
}

return res;
}
``````

Alternatively, we can calculate the rang first, then insert into buckets. Credit to @Jinx_boom

``````public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> cols = new ArrayList<>();
if (root == null) {
return cols;
}

int[] range = new int[] {0, 0};
getRange(root, range, 0);

for (int i = range[0]; i <= range[1]; i++) {
}

while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int col = colQueue.poll();

if (node.left != null) {
}
if (node.right != null) {
}
}

return cols;
}

public void getRange(TreeNode root, int[] range, int col) {
if (root == null) {
return;
}
range[0] = Math.min(range[0], col);
range[1] = Math.max(range[1], col);

getRange(root.left, range, col - 1);
getRange(root.right, range, col + 1);
}``````

• Similar idea with TreeMap.

``````public int index = 0;
public TreeMap<Integer, List<Integer>> tm;

public class Pair {
TreeNode node;
int index;
public Pair(TreeNode n, int i) {
node = n;
index = i;
}
}

public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
tm = new TreeMap<Integer, List<Integer>>();
if (root == null) return res;

q.offer(new Pair(root, 0));

while (!q.isEmpty()) {
Pair cur = q.poll();
if (!tm.containsKey(cur.index)) tm.put(cur.index, new ArrayList<Integer>());

if (cur.node.left != null) q.offer(new Pair(cur.node.left, cur.index-1));
if (cur.node.right != null) q.offer(new Pair(cur.node.right, cur.index+1));
}

for (int key : tm.keySet()) res.add(tm.get(key));
return res;
}``````

• It seems your algorithm is not right. Given a perfect 4-level binary tree, named by level: 1; 2,3; 4,5,6,7; 8,9,10,11,12,13,14,15, I got this result: [[8], [4], [2, 9, 10, 12], [1, 5, 6], [3, 11, 13, 14], [7], [15]]. See 12 runs into a bucket ahead of 11's. I don't think that's right. The correct answer should be [[8],[4],[2,9,10],[5],[1,11,12],[6],[3,13,14],[7],[15]]. Draw the tree on a paper, you'll see.

• @nick46, thanks for your question. It is correct. At first I had the same confusion as you. `12` do appear on the left of `11`. By saying vertical order, IMO, each node at each level has the same width, please see my updated post for more clarification.

• Also a bit subtle is why the problem requires a BFS instead of say DFS(which is what I tried).
@yavinci It would be worth mentioning in the explanation that since the nodes in a column are ordered by their row number(depth) we cannot process level x+2 nodes before we process level x.
If you do DFS, the result has the same List<Integer> elements but in the wrong order.

• cpp solution using BFS.

``````class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
map<int,vector<int>> hm;
queue<pair<TreeNode*,int>> q;
q.push({root,0});
while(!q.empty()){
TreeNode* node=q.front().first;
int col=q.front().second;
q.pop();
hm[col].push_back(node->val);
if(node->left) q.push({node->left,col-1});
if(node->right) q.push({node->right,col+1});
}
for(auto i:hm){
res.push_back(i.second);
}
return res;
}
``````

};

• Definitely one of the smartest and cleanest solution, with detailed explanations I've ever seen on LC.
Thx for sharing

• Thanks for bringing up the problem with DFS. I was wondering why can't we use DFS.

• Memory Limit Exceeded

• Useful tip for Java 8 users:

`if(!map.containsKey(col)) map.put(col, new ArrayList<Integer>());`

can be replaced with:

`map.putIfAbsent(col, new ArrayList<>());`

• Similar idea, integrate the node and corresponding col num into a new class.

``````class Node {
TreeNode node;
int col;
public Node(TreeNode node, int col) {
this.node = node;
this.col = col;
}
}
public class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null)   return res;
queue.offer(new Node(root, 0));
Map<Integer, List<Integer>> map = new HashMap<>();
int min = 0, max = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
// update map
if (!map.containsKey(cur.col))  map.put(cur.col, new ArrayList<Integer>());

if (cur.node.left != null) {
queue.offer(new Node(cur.node.left, cur.col-1));
min = Math.min(cur.col-1, min);
}
if (cur.node.right != null) {
queue.offer(new Node(cur.node.right, cur.col+1));
max = Math.max(cur.col+1, max);
}
}
// iterate the map
for (int i = min; i <= max; i++) {
}
return res;
}
}
``````

• @darrenxyli Very smart idea! I'm confused about what is vertical order for a while... The last for-loop seems to be redundant, right? Since TreeMap.values() will return a view in ascending order. Thanks for your sharing!

``````    public List<List<Integer>> verticalOrder(TreeNode root) {
Map<Integer,List<Integer>> idxNode = new TreeMap<>();
if (root != null) q.offer(new Pair(0, root));
while (!q.isEmpty()) {
Pair p = q.poll();
if (!idxNode.containsKey(p.idx))
idxNode.put(p.idx, new ArrayList<>());

if (p.node.left != null) q.offer(new Pair(p.idx - 1, p.node.left));
if (p.node.right != null) q.offer(new Pair(p.idx + 1, p.node.right));
}
return new ArrayList<>(idxNode.values());
}
``````

ps: I realize that the time complexity will be O(NlogN) using TreeMap sadly... So I change my mind to use HashMap in order to maintain O(N) time.

``````    public List<List<Integer>> verticalOrder(TreeNode root) {
Map<Integer,List<Integer>> colNode = new HashMap<>();
if (root != null) q.offer(new Pair(0, root));
int min = 0, max = 0;
while (!q.isEmpty()) {
Pair p = q.poll();
if (!colNode.containsKey(p.col))
colNode.put(p.col, new ArrayList<>());
min = Math.min(min, p.col);
max = Math.max(max, p.col);

if (p.node.left != null) q.offer(new Pair(p.col - 1, p.node.left));
if (p.node.right != null) q.offer(new Pair(p.col + 1, p.node.right));
}
List<List<Integer>> ret = new ArrayList<>();
for (int i = min; i <= max; i++) ret.add(colNode.get(i));
return ret;
}
``````

• Please anyone put @yavinci 's explanation of `width` into this question's description field.

Much appreciated!

• I believe we don't need to calculate min and max anyway

``````public class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
if(root==null) return res;

Map<Integer,List<Integer>> map = new HashMap<>();

nodeQueue.offer(root);
levelQueue.offer(0);
while(!nodeQueue.isEmpty()){
TreeNode node = nodeQueue.poll();
int level = levelQueue.poll();
if(!map.containsKey(level)){
map.put(level,list);
}
if(node.left!=null){
nodeQueue.offer(node.left);
levelQueue.offer(level-1);
}
if(node.right!=null){
nodeQueue.offer(node.right);
levelQueue.offer(level+1);
}
}
return res;
}
}
``````

• Very Clean Code!!!!!!!

• Can I use stack instead of queue?

• @jessebest It's level based traversal, you'd better use queue. If you want to use stack, you can `implement queue with stack` also, which is another question in LeetCode. :)

• @wei_fy
Thanks for the nice code! FWIW, the transform from hm to res can move the items over instead of copying:

``````for(auto& i : hm)
res.push_back(move(i.second));
``````

• The following solution does not pass the test below (because of the order of 8 and 2).
Can anyone help me to understand what I did wrong please?

Input:
[3,9,8,4,0,1,7,null,null,null,2,5]
Output:
[[4],[9,5],[3,0,1],[2,8],[7]]
Expected:
[[4],[9,5],[3,0,1],[8,2],[7]]

``````public List<List<Integer>> verticalOrder(TreeNode root) {
Map<Integer,List<Integer>> map = new TreeMap<Integer, List<Integer>>();
verticalOrderHelper(root,map,0);
List<List<Integer>> result = new ArrayList<List<Integer>>(map.values());
return result;
}

public void verticalOrderHelper(TreeNode root,Map<Integer,List<Integer>> map,Integer level){
if (root == null) return;
List<Integer> list = map.get(level);
if (list==null)
list = new ArrayList<Integer>();
map.put(level, list);
verticalOrderHelper(root.left,map,level-1);
verticalOrderHelper(root.right,map,level+1);
}
``````

• My Javascript version:

``````const verticalOrder = (root) => {
if (root === null) return [];
let [min, max] = getRange(root, [0, 0], 0);
let queue = [];
let result = Array(max - min + 1).fill().map(() => Array());
queue.push([0, root]);
while(queue.length !== 0) {
let [curIdx, curNode] = queue.shift();
result[curIdx - min].push(curNode.val);
curNode.left !== null && queue.push([curIdx - 1, curNode.left]);
curNode.right !== null && queue.push([curIdx + 1, curNode.right]);
}
return result;
};

const getRange = (root, range, col) => {
if (root === null) {
return range;
}
range = [Math.min(range[0], col), Math.max(range[1], col)];
range = getRange(root.left, range, col-1);
range = getRange(root.right, range, col+1);
return range;
};
``````

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