| 11 | { |
| 12 | //Function to return a list containing the bottom view of the given tree. |
| 13 | public ArrayList <Integer> bottomView(Node root) |
| 14 | { |
| 15 | // Code here |
| 16 | |
| 17 | ArrayList<Integer> ans = new ArrayList<>(); |
| 18 | if(root == null) return ans; |
| 19 | TreeMap<Integer, Integer> map = new TreeMap<>(); |
| 20 | Queue<Pair> q = new LinkedList<>(); |
| 21 | q.add(new Pair(root,0)); |
| 22 | while(!q.isEmpty()) { |
| 23 | Pair temp = q.remove(); |
| 24 | int v = temp.vertical; |
| 25 | Node n = temp.node; |
| 26 | map.put(v, n.data); |
| 27 | if(n.left != null) { |
| 28 | q.add(new Pair(n.left,v-1)); |
| 29 | } |
| 30 | if(n.right != null) { |
| 31 | q.add(new Pair(n.right,v+1)); |
| 32 | } |
| 33 | } |
| 34 | |
| 35 | for (Map.Entry<Integer,Integer> entry : map.entrySet()) { |
| 36 | ans.add(entry.getValue()); |
| 37 | } |
| 38 | return ans; |
| 39 | } |
| 40 | } |