vertical order BST in dfs and bfs

VerticalOrderBST.java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class VerticalOrderBST {
    
    /**
     * DFS
     * @param root: the root of tree
     * @return: the vertical order traversal
     */
    public List<List<Integer>> verticalOrder(TreeNode root) {
        // write your code here
        if (root == null) return new ArrayList<>();
        
        Map<Integer, List<Pair>> map = new TreeMap<>();
        dfs(root, 0, 0, map);
        List<List<Integer>> ans = new ArrayList<>();
        for (Map.Entry<Integer, List<Pair>> entry : map.entrySet()) {
            List<Pair> cols = entry.getValue();
            Collections.sort(cols, (Pair p1, Pair p2) -> (p1.row - p2.row));
            List<Integer> one = new ArrayList<>();
            for (Pair pair : cols) {
                one.add(pair.val);
            }
            ans.add(one);

        }
        return ans;
    }
    
    private void dfs(TreeNode root, int row, int col, Map<Integer, List<Pair>> map) {
        if (root == null) return;
        if (!map.containsKey(col)) {
            map.put(col, new ArrayList<>());
        }
        map.get(col).add(new Pair(row, col, root.val));
        dfs(root.left, row + 1, col - 1, map);
        dfs(root.right, row + 1, col + 1, map);
    }

    private class Pair {
        public int row = 0;
        public int col = 0;
        public int val = 0;
        
        public Pair(int row, int col, int val) {
            this.row = row;
            this.col = col;
            this.val = val;
        }
    }
    
    // bfs
     /**
     * @param root: the root of tree
     * @return: the vertical order traversal
     */
    public List<List<Integer>> verticalOrder(TreeNode root) {
        // write your code here
        if (root == null) return new ArrayList<>();
        
        Map<Integer, List<Integer>> map = new TreeMap<>();
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(0, root));
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                Pair pair = q.poll();
                int col = pair.col;
                TreeNode nd = pair.nd;
                if (!map.containsKey(col)) {
                    map.put(col, new ArrayList<>());
                }
                map.get(col).add(nd.val);
                if (nd.left != null) {
                    q.offer(new Pair(col - 1, nd.left));
                }
                if (nd.right != null) {
                    q.offer(new Pair(col + 1, nd.right));
                }
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            ans.add(entry.getValue());
        }
        return ans;
    }

    private class Pair {
        public int col = 0;
        public TreeNode nd = null;
        
        public Pair(int col, TreeNode nd) {
            this.col = col;
            this.nd = nd;
        }
    }

}