Bottom View

Info

Just remove the check from Top View’s answer to ensure we consider the bottommost node at each horizontal level.

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> bottomView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
 
        // Use TreeMap to store horizontal distance as key and node value as value
        // TreeMap maintains keys in sorted order, helping in getting bottom 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;
 
            // Update the map with the latest node value encountered at each horizontal distance
            // This ensures we consider the bottommost node at each horizontal distance
            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 bottom view node values from map to result list
        for (int value : mapHorizontalDistance.values()) {
            result.add(value);
        }
 
        return result;
    }
}