import java.util.*;
class Pair<U, V> {
public U first;
public V second;
public Pair(U first, V second) {
this.first = first;
this.second = second;
}
}
public class Solution {
private static List<Integer> getBottomView(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if(root == null) {
return ans;
}
Map<Integer, Integer> treeMap = new TreeMap<>();
Queue<Pair<Integer, TreeNode>> pendingNodes = new LinkedList<>();
pendingNodes.offer(new Pair<>(0, root));
while(!pendingNodes.isEmpty()) {
Pair<Integer, TreeNode> front = pendingNodes.poll();
treeMap.put(front.first, front.second.val);
if(front.second.left != null) {
pendingNodes.offer(new Pair<>(front.first-1, front.second.left));
}
if(front.second.right != null) {
pendingNodes.offer(new Pair<>(front.first+1, front.second.right));
}
}
for(Map.Entry<Integer, Integer> entries: treeMap.entrySet()) {
ans.add(entries.getValue());
}
return ans;
}
public static List<Integer> bottomView(TreeNode root) {
// Write your code here.
return getBottomView(root);
}
}