Bottom View of Binary Tree

Problem Statement

Given a binary tree, return an array where elements represent the bottom view of the binary tree from left to right.(GFG link)

Note: If there are multiple bottom-most nodes for a horizontal distance from the root, then the later one in the level order traversal is considered. For example, in the below diagram, 7 and 34 both are the bottommost nodes at a horizontal distance of 0 from the root, here 34 will be considered.

For the above tree, the output should be 5 8 34 22 25

Examples :

Input: root[] = [1, 3, 2]

Output: [3 1 2]

Explanation: First case represents a tree with 3 nodes and 2 edges where root is 1, left child of 1 is 3 and right child of 1 is 2.

Thus bottom view of the binary tree will be 3 1 2.

Input: root[] = [10, 20, 30, 40, 60]

Output: [40 20 60 30]

Solution (BFS)

This is an application of vertical order traversal.

• We maintain a column map to track which elements are in each column.

• In the column map, we store the most recent element by overwriting the previous one, which gives us the bottom view.

• If two elements have the same column and row number, we prioritize the right element.

Time - O(n)

Space - O(n)

class Solution {

    private class Pair{
      Node node;
      int column;

      Pair(Node node, int column){
          this.node = node;
          this.column = column;
      }
    }

    private Map<Integer, Integer> buildMap(Node root){
        Queue<Pair> queue = new ArrayDeque<>();
        queue.add(new Pair(root,0));
        Map<Integer, Integer> columnMap = new TreeMap<>();

        while(!queue.isEmpty()){
          Pair pair = queue.poll();
          Node node = pair.node;
          int column = pair.column;
          columnMap.put(column, node.data);

          if(node.left!=null){
            queue.add(new Pair(node.left, column-1));
          }
          if(node.right!=null){
            queue.add(new Pair(node.right, column+1));
          }
        }
        return columnMap;
    }

    public ArrayList<Integer> bottomView(Node root) {
      Map<Integer, Integer> columnMap = buildMap(root);
      ArrayList<Integer> view = new ArrayList<>();
      for(Integer element: columnMap.values()){
        view.add(element);
      }
      return view;
    }

}

Note:

If we want to build a map using DFS, the above approach won't work because overwriting the map with the most recent element might mean it's not the bottom element.