# HashMap + BFS solution in Java

• The idea is quite straightforward: first store the vertical order of every node in a HashMap. Then use BFS to traverse the tree and add node values to the correct location of the list.

Java code:

``````public class Solution {
private HashMap<TreeNode, Integer> nodeValColId;
private List<List<Integer>> list;
private int min, max;
public List<List<Integer>> verticalOrder(TreeNode root) {
list = new ArrayList<>();

if(root == null) return list;

min = max = 0;
nodeValColId = new HashMap<>();
nodeValColId.put(root, 0);

getNodeColId(root, 0);

for(int i=min; i<=max; i++) {
list.add(new ArrayList<>()); // initialize the list
}

// BFS traversal of the tree
while(!q.isEmpty()) {
TreeNode current = q.peek();
q.poll();
int level = nodeValColId.get(current);
List<Integer> innerList = new ArrayList<>();
if(current.left!=null)
if(current.right!=null)
}

return list;
}
// compute the vertical order of all nodes
private void getNodeColId(TreeNode root, int rootColId) {
if(root.left!=null) {
nodeValColId.put(root.left, rootColId-1);
getNodeColId(root.left, rootColId-1);
min = rootColId-1 < min ? rootColId-1 : min;
}
if(root.right!=null) {
nodeValColId.put(root.right, rootColId+1);
getNodeColId(root.right, rootColId+1);
max = rootColId+1 > max ? rootColId+1 : max;
}
}
}``````

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