Vertical Order Traversal of a Binary Tree

Java

class Solution {
    static class Pair implements Comparable<Pair> {
        int val;
        int pos;
        public Pair(int val, int pos) {
            this.val = val;
            this.pos = pos;
        }
        
        @Override
        public int compareTo(Pair o) {
            int compare = Integer.compare(o.pos, pos);
            if (compare != 0) {
                return compare;
            }
            return Integer.compare(val, o.val);
        }
    }
    
    Map<Integer, PriorityQueue<Pair>> map;
    int min;
    int max;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map = new HashMap<>();
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
        helper(root, 0, 0);
        List<List<Integer>> result = new ArrayList<>(max - min);
        for (int i = min; i <= max; i++) {
            PriorityQueue<Pair> pq = map.get(i);
            List<Integer> list = new ArrayList<>(pq.size());
            while (!pq.isEmpty()) {
                list.add(pq.poll().val);
            }
            result.add(list);
        }
        return result;
    }
    
    private void helper(TreeNode node, int verticalLevel, int horizontalLevel) {
        if (node == null) {
            return;
        }
        min = Math.min(min, verticalLevel);
        max = Math.max(max, verticalLevel);
        map.computeIfAbsent(verticalLevel, k -> new PriorityQueue<>()).offer(new Pair(node.val, horizontalLevel));
        helper(node.left, verticalLevel - 1, horizontalLevel - 1);
        helper(node.right, verticalLevel + 1, horizontalLevel - 1);
    }
}