L23: Bottom View of Binary Tree

The Bottom View of a Binary Tree is the set of nodes visible when the tree is viewed from a straight, bottom-up perspective onto a 1D plane. When multiple nodes overlap vertically at the same horizontal coordinate (column), the node that appears physically lowest in the structural hierarchy—specifically, the rightmost node encountered during a level-order traversal—overwrites any nodes above it to form the final bottom view.

1. Problem Statement & The "1D Projection" Mental Model

Imagine standing directly underneath a binary tree and looking straight up. Nodes that are positioned directly above other nodes will be obscured, while the lowest visible nodes along each vertical coordinate will form our silhouette.

Real-Life Analogy: Projecting Shadows

Think of shining a powerful vertical spotlight straight down from the ceiling onto a binary tree resting on the floor.

• Nodes directly above other nodes cast shadows that cover the nodes beneath them.
• However, for our bottom view, we want the exact opposite of a shadow: we want to capture the deepest node that successfully hits the floor at any given horizontal position. If two nodes compete for the exact same vertical line coordinate, the node that is processed later in a standard level-order sweep (or the rightmost node at that level/coordinate) takes precedence.

Consider the following example tree:

         1
       /   \
      2     3
     / \   / \
    4   5 6   7
       / \
      8   9

Mapping out the visible bottom nodes from left to right:

• Line -2: Node 4
• Line -1: Node 8 (hiding node 2)
• Line 0: Nodes 5 and 6 compete; the rightmost wins (6)
• Line 1: Node 9 (hiding node 3)
• Line 2: Node 7

Final Bottom View Result: [4, 8, 6, 9, 7]

2. Leveraging the Vertical Line Concept

To solve this systematically, we build upon the vertical order traversal coordinate system (originally introduced for vertical slicing):

• Assign the root node a horizontal distance coordinate (often called hd or line) of 0.
• Moving to any left child decreases the horizontal distance by 1 (hd - 1).
• Moving to any right child increases the horizontal distance by 1 (hd + 1).

Line Coordinates:
  -2    -1     0     1     2
         (1: hd=0)
        /         \
   (2: hd=-1)   (3: hd=1)
   /      \     /       \
(4:hd=-2)(5:hd=0)(6:hd=0)(7:hd=2)
         /     \
    (8:hd=-1) (9:hd=1)

By mapping every vertical line coordinate to its corresponding node, we can determine the bottom view. Because nodes lower down in a level-order traversal overwrite earlier nodes at the same coordinate, an iterative traversal naturally resolves overlaps correctly.

3. Data Structure Design: Queue + Self-Balancing Map

To execute this efficiently, we use two fundamental data structures:

1. Queue (std::queue / java.util.Queue): Facilitates the Breadth-First Search (BFS) / Level-Order Traversal, tracking both the tree node and its associated horizontal line coordinate.
2. Ordered Map (std::map / java.util.TreeMap): Stores pairs of (horizontal_distance -> node_value). An ordered map automatically sorts its keys in ascending order (from negative left coordinates to positive right coordinates), making it trivial to extract our final result left-to-right.

4. Step-by-Step Level-Order Flow Walkthrough

Let's trace the algorithm step-by-step using our example tree:

Queue is now empty. Extracting values from the map in sorted key order gives: [4, 8, 6, 9, 7].

5. Complete C++ Implementation

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> bottomView(Node* root) {
        vector<int> ans;
        if (root == nullptr) {
            return ans;
        }
        
        // Map to store the last node at each horizontal distance (line)
        // Key: Horizontal Distance, Value: Node Data
        map<int, int> mpp;
        
        // Queue for level order traversal storing pairs of (Node*, Horizontal Distance)
        queue<pair<Node*, int>> q;
        
        q.push({root, 0});
        
        while (!q.empty()) {
            auto it = q.front();
            q.pop();
            
            Node* node = it.first;
            int line = it.second;
            
            // Overwrite the value for this line; the last one processed wins
            mpp[line] = node->data;
            
            // Traverse left child (line - 1)
            if (node->left != nullptr) {
                q.push({node->left, line - 1});
            }
            
            // Traverse right child (line + 1)
            if (node->right != nullptr) {
                q.push({node->right, line + 1});
            }
        }
        
        // Extract values from the sorted map into the result vector
        for (auto it : mpp) {
            ans.push_back(it.second);
        }
        
        return ans;
    }
};

6. Complete Java Implementation

import java.util.*;

class Node {
    int data;
    Node left, right;
    
    Node(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class Pair {
    Node node;
    int hd; // Horizontal Distance
    
    Pair(Node node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}

class Solution {
    public ArrayList<Integer> bottomView(Node root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        
        // TreeMap keeps the keys (horizontal distances) sorted automatically
        Map<Integer, Integer> map = new TreeMap<>();
        Queue<Pair> queue = new LinkedList<>();
        
        queue.add(new Pair(root, 0));
        
        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            Node node = current.node;
            int hd = current.hd;
            
            // Update map with current node data for this horizontal distance
            map.put(hd, node.data);
            
            // Push left child with hd - 1
            if (node.left != null) {
                queue.add(new Pair(node.left, hd - 1));
            }
            
            // Push right child with hd + 1
            if (node.right != null) {
                queue.add(new Pair(node.right, hd + 1));
            }
        }
        
        // Collect values from the sorted map
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ans.add(entry.getValue());
        }
        
        return ans;
    }
}

7. Why Recursive Traversals Fail Here (The Pitfall)

You might wonder: "Can we solve this using standard DFS recursion (like In-order, Pre-order, or Post-order) by passing down the line coordinate?"

The Issue with Recursion

• Standard recursive traversals visit nodes in depth-first order rather than level-by-level order.
• If a deep left branch visits line 0 after a shallower right branch has already registered its node for line 0, the recursive DFS approach can incorrectly overwrite the bottom-most node with an upper-level node.
• The Fix: If you attempt a recursive solution, you must track both the horizontal distance (hd) and the vertical depth/level. You would need to store objects containing (node_value, depth) in your map, only replacing the node if the incoming node's depth is greater than or equal to the stored depth.

Because of this unnecessary complexity, Level-Order Traversal (BFS) remains the cleanest, most intuitive, and industry-standard approach.

8. Complexity Analysis

• Time Complexity: $\mathcal{O}(N \log N)$, where $N$ is the number of nodes in the binary tree.
  • Reasoning: Every node is visited once during the BFS queue traversal ($\mathcal{O}(N)$). Inserting or updating elements in a self-balancing binary search tree map (std::map / TreeMap) takes $\mathcal{O}(\log K)$ time per insertion, where $K$ is the number of distinct horizontal lines (at most $N$).
• Space Complexity: $\mathcal{O}(N)$.
  • Reasoning: In the worst-case scenario (such as a complete binary tree), the queue holds up to roughly $N/2$ leaf nodes at the bottom level, and the map stores up to $N$ unique horizontal line coordinates.

Summary and Key Takeaways

• Core Objective: The bottom view renders the lowest visible node at every vertical coordinate column across a binary tree.
• Rightmost Precedence: When multiple nodes overlap on the same vertical line, the node processed later in level order (the rightmost node) takes priority.
• Coordinate Tracking: We use a horizontal distance integer (hd), where moving left is hd - 1 and moving right is hd + 1.
• Data Structure Synergy: Combining a Queue (for BFS level-order traversal) with an Ordered Map / TreeMap (for automatic coordinate sorting) provides an elegant, optimal solution.
• Avoid Naive Recursion: Standard recursive DFS fails without explicit depth tracking because it visits nodes out of level-order sequence; BFS naturally processes nodes from top to bottom.
• Optimal Efficiency: Achieves an optimal $\mathcal{O}(N \log N)$ time and $\mathcal{O}(N)$ space complexity.