Top View

import java.util.*;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
 
    TreeNode(int val) {
        this.val = val;
    }
}
 
class Solution {
 
    // Pair class to store node and its horizontal distance
    class Pair {
        TreeNode node;
        int horizontalDistance;
 
        Pair(TreeNode node, int horizontalDistance) {
            this.node = node;
            this.horizontalDistance = horizontalDistance;
        }
    }
    
    public List<Integer> topView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
 
        // Use TreeMap to store horizontal distance (or level) as key and node value as value
        // TreeMap maintains keys in sorted order, helping in getting top view nodes from left to right
        Map<Integer, Integer> mapHorizontalDistance = new TreeMap<>();
 
        // Use queue for level-order traversal
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(root, 0));
 
        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            TreeNode node = current.node;
            int horizontalDistance = current.horizontalDistance;
 
            // Add node value to map only if horizontal distance is not already present
            // This ensures we consider only the topmost node at each horizontal distance
            if (!mapHorizontalDistance.containsKey(horizontalDistance)) {
                mapHorizontalDistance.put(horizontalDistance, node.val);
            }
 
            // Add left child to queue with horizontal distance decreased by 1
            if (node.left != null) {
                queue.offer(new Pair(node.left, horizontalDistance - 1));
            }
 
            // Add right child to queue with horizontal distance increased by 1
            if (node.right != null) {
                queue.offer(new Pair(node.right, horizontalDistance + 1));
            }
        }
 
        // Add top view node values from map to result list
        for (int value : mapHorizontalDistance.values()) {
            result.add(value);
        }
 
        return result;
    }
}