class Solution{
    //Function to return a list containing the bottom view of the given tree.
    public ArrayList <Integer> bottomView(Node root){
        // Code here
        
         
    
        // Code here
        
        Queue<Pair> q = new ArrayDeque<>();
        
        TreeMap<Integer,Integer> mpp=new TreeMap<>();
        
        q.add(new Pair(0,root));
        
        while(!q.isEmpty()){
            Pair curr = q.poll();
            mpp.put(curr.hd,curr.node.data);
            
            if(curr.node.left!=null){
                q.add(new Pair(curr.hd-1,curr.node.left));
            }
            if(curr.node.right!=null){
                q.add(new Pair(curr.hd+1,curr.node.right));
            }
        }
        
        
        ArrayList<Integer> res = new ArrayList<>();
        
        for(Map.Entry<Integer,Integer> entry: mpp.entrySet()){
            res.add(entry.getValue());
        }
        
        
        return res;
        
        
        
    }
    
    static class Pair{
        int hd;
        Node node;
        
        public Pair(int hd,Node node){
            this.hd=hd;
            this.node = node;
        }
    }
    
    
    
    
    
    
}