# BFS&DFS Java solution using predefined class instead of two queues

• BFS solution

``````class Node{
private TreeNode node;
private int pos;
public Node(TreeNode node, int pos){
this.node = node;
this.pos = pos;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
Queue<Node> q = new LinkedList<Node>();
q.offer(new Node(root, 0));
while(!q.isEmpty()){
Node cur = q.poll();
TreeNode node = cur.node;
int pos = cur.pos;
if(!map.containsKey(pos))
map.put(pos, new ArrayList<Integer>());
min = Math.min(min, pos);
max = Math.max(max, pos);
if(node.left != null) q.offer(new Node(node.left, pos - 1));
if(node.right != null) q.offer(new Node(node.right, pos + 1));
}
for(int i = min; i <= max; i ++){
}
return res;
}
``````

DFS
The DFS solution cannot get AC with the test case `[3,9,8,4,0,1,7,null,null,null,2,5]`
The expected output should be `[[4],[9,5],[3,0,1],[8,2],[7]]` while mine is `[[4],[9,5],[3,0,1],[2,8],[7]]`. I see the difference but dont quite understand why the sequence of output brings fault.

``````class Node{
private TreeNode node;
private int pos;
public Node(TreeNode node, int pos){
this.node = node;
this.pos = pos;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
Queue<Node> q = new LinkedList<Node>();
q.offer(new Node(root, 0));
while(!q.isEmpty()){
Node cur = q.poll();
TreeNode node = cur.node;
int pos = cur.pos;
if(!map.containsKey(pos))
map.put(pos, new ArrayList<Integer>());
min = Math.min(min, pos);
max = Math.max(max, pos);
if(node.left != null) q.offer(new Node(node.left, pos - 1));
if(node.right != null) q.offer(new Node(node.right, pos + 1));
}
for(int i = min; i <= max; i ++){