Vertical Order Traversal

Solution

class Solution {
    class Pair {
        TreeNode node;
        int hd;
        int level;
        
        public Pair(TreeNode node, int hd, int level) {
            this.node = node;
            this.hd = hd;
            this.level = level;
        }
    }
 
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();
 
        List<List<Integer>> result = new ArrayList<>();
        
        // TreeMap to store the nodes at each horizontal distance (Visualised Below!)
        TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
        
        // Queue to perform level-order traversal
        Queue<Pair> queue = new LinkedList<>();
        
        // Start with the root node at horizontal distance 0 and level 0
        queue.add(new Pair(root, 0, 0));
        
        while (!queue.isEmpty()) {
            Pair temp = queue.poll();
            TreeNode node = temp.node;
            int hd = temp.hd;
            int level = temp.level;
            
            // If the horizontal distance is not present in the map, add it
            if (!map.containsKey(hd)) {
                map.put(hd, new TreeMap<>());
            }
            // If the level is not present at this horizontal distance, add it
            if (!map.get(hd).containsKey(level)) {
                map.get(hd).put(level, new PriorityQueue<>());
            }
            // Add the current node to the priority queue for its horizontal distance and level
            map.get(hd).get(level).add(node.val);
            
            // Enqueue left child with horizontal distance hd - 1 and level + 1
            if (node.left != null) {
                queue.add(new Pair(node.left, hd - 1, level + 1));
            }
            
            // Enqueue right child with horizontal distance hd + 1 and level + 1
            if (node.right != null) {
                queue.add(new Pair(node.right, hd + 1, level + 1));
            }
        }
        
 
        for (TreeMap<Integer, PriorityQueue<Integer>> levels : map.values()) {
            List<Integer> vertical = new ArrayList<>();
            for (PriorityQueue<Integer> nodes : levels.values()) {
                while (!nodes.isEmpty()) {
                    vertical.add(nodes.poll());
                }
            }
            result.add(vertical);
        }
 
        return result;
    
    }
}

Visualization of data structure to store the values:

 
TreeMap<Integer, 
		TreeMap<Integer, 
				PriorityQueue<Integer>>> 
		map = new TreeMap<>();
 
map = {
    -2: {
        2: [4]
    },
    -1: {
        1: [2]
    },
    0: {
        0: [1],
        2: [5, 6]
    },
    1: {
        1: [3]
    },
    2: {
        2: [7]
    }
}