# Java solution using Double Linked List

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

Set<TreeNode> visited = new HashSet<TreeNode>();
queue.offer(root);

Map<TreeNode, NodeList> nodeListMap = new HashMap<TreeNode, NodeList>();

while(!queue.isEmpty()){
TreeNode top = queue.poll();
NodeList cur = nodeListMap.get(top);

queue.offer(top.left);
if(cur.left == null){
cur.left = new NodeList();
cur.left.right = cur;
}

nodeListMap.put(top.left, cur.left);
}

queue.offer(top.right);
if(cur.right == null){
cur.right = new NodeList();
cur.right.left = cur;
}
nodeListMap.put(top.right, cur.right);
}
}

List<Integer> nodeCols = new ArrayList<Integer>();
}
}

return result;
}

private static class NodeList{
NodeList left;
NodeList right;
List<Integer> nodes = new ArrayList<Integer>();
}
``````

Linked list can be replaces by using another queue to track the index, below is the modified above snippet

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

int minIdx = 0, maxIdx = 0;

Set<TreeNode> visited = new HashSet<TreeNode>();
queue.offer(root);

Map<Integer, List<Integer>> nodeListMap = new HashMap<Integer, List<Integer>>();
nodeListMap.put(0, new ArrayList<Integer>());

while(!queue.isEmpty()){
TreeNode top = queue.poll();
int idx = colQueue.poll();

minIdx = Math.min(minIdx, idx);
maxIdx = Math.max(maxIdx, idx);

queue.offer(top.left);
colQueue.offer(idx-1);
if(!nodeListMap.containsKey(idx - 1)){
nodeListMap.put(idx-1, new ArrayList<Integer>());
}
}

queue.offer(top.right);
colQueue.offer(idx+1);
if(!nodeListMap.containsKey(idx + 1)){
nodeListMap.put(idx+1, new ArrayList<Integer>());
}
}
}

for(int i=minIdx; i<=maxIdx; i++){