Bottom View for Level Order Traversal

import java.util.*;

// TreeNode definition as before

class Tuple {
    TreeNode node;
    int vertical;
    int level;

    Tuple(TreeNode node, int vertical, int level) {
        this.node = node;
        this.vertical = vertical;
        this.level = level;
    }
}

class Solution {
    public List<Integer> bottomView(TreeNode root) {
        // TreeMap to store vertical -> node value at the lowest level
        TreeMap<Integer, Tuple> map = new TreeMap<>();
        
        // Queue to store the node, vertical, and level
        Queue<Tuple> q = new LinkedList<>();
        
        // Initialize the queue with the root node at vertical level 0
        q.offer(new Tuple(root, 0, 0));
        
        while (!q.isEmpty()) {
            Tuple tuple = q.poll();
            TreeNode node = tuple.node;
            int vertical = tuple.vertical;
            int level = tuple.level;
            
            // If the vertical is not in the map, or if the current level is deeper, update the map
            if (!map.containsKey(vertical) || map.get(vertical).level <= level) {
                map.put(vertical, tuple); // Store the node at this vertical with its level
            }
            
            // Enqueue left and right child nodes with their respective vertical levels and incremented level
            if (node.left != null) {
                q.offer(new Tuple(node.left, vertical - 1, level + 1)); // Left child goes to vertical - 1
            }
            if (node.right != null) {
                q.offer(new Tuple(node.right, vertical + 1, level + 1)); // Right child goes to vertical + 1
            }
        }
        
        // Prepare the result from the map: Just extract the node values
        List<Integer> result = new ArrayList<>();
        for (Tuple tuple : map.values()) {
            result.add(tuple.node.val);
        }
        return result;
    }
}