# BFS Solution - Java - Accepted 9ms

• The correct solution here is the BFS way. Else maintaining the ordering becomes a nightmare.

public class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
// Map which keys on horizontal distance from the root
// Any traversal on right is +1 and any traversal on left is -1

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

if (root == null) return retList;

int hd = 0, depth = 0;
bfs(map, root);

// Sort they keys in increasing order
Integer[] keys = map.keySet().toArray(new Integer[map.keySet().size()]);
Arrays.sort(keys);

for (int key : keys) {
retList.add(map.get(key));
}
return retList;
}

void bfs(Map<Integer, List<Integer>> map, TreeNode root) {
Deque<TreeNode> nodeQue = new ArrayDeque<TreeNode>();
Deque<Integer> hdQue = new ArrayDeque<Integer>();

nodeQue.offer(root);
hdQue.offer(0);

while (!nodeQue.isEmpty()) {
root = nodeQue.pollFirst();
int hd = hdQue.pollFirst();

if (!map.containsKey(hd)) {
map.put(hd, new ArrayList<Integer>());
}
map.get(hd).add(root.val);

if (root.left!=null) {
nodeQue.offer(root.left); hdQue.offer(hd-1);
}
if (root.right != null) {
nodeQue.offer(root.right); hdQue.offer(hd+1);
}
}
}
}

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