Bottom View of Binary Tree in DSA C++

Mental Model

We want to see the nodes visible if we look at the tree from the bottom. Each vertical line shows the lowest node at that horizontal distance.

Analogy: Imagine standing under a tree and looking up. The bottom view shows the leaves and branches you can see directly above you, ignoring anything hidden behind.

       20
      /  \
    8     22
   / \      \
  5   3      25
     / \      
    10  14    

Horizontal distances:
-2   -1    0    1    2
 5 ->10 -> 3 ->14 ->25

Dry Run Walkthrough

Input: Binary tree: 20 / \ 8 22 / \ \ 5 3 25 / \ 10 14 Find bottom view

Goal: Find nodes visible from bottom, one per horizontal distance, showing the lowest node at each horizontal distance

Step 1: Start BFS from root (20) at horizontal distance 0

Map: {0: 20}
Queue: [(20,0)]

Why: Initialize with root node at horizontal distance 0

Step 2: Pop (20,0), add left child (8,-1) and right child (22,1)

Map: {0: 20}
Queue: [(8,-1), (22,1)]

Why: Add children with updated horizontal distances

Step 3: Pop (8,-1), add left child (5,-2) and right child (3,0), update map at -1

Map: {-1: 8, 0: 20}
Queue: [(22,1), (5,-2), (3,0)]

Why: Update bottom view for horizontal distance -1 and add children

Step 4: Pop (22,1), add right child (25,2), update map at 1

Map: {-1: 8, 0: 20, 1: 22}
Queue: [(5,-2), (3,0), (25,2)]

Why: Update bottom view for horizontal distance 1 and add child

Step 5: Pop (5,-2), no children, update map at -2

Map: {-2: 5, -1: 8, 0: 20, 1: 22}
Queue: [(3,0), (25,2)]

Why: Update bottom view for horizontal distance -2

Step 6: Pop (3,0), add left child (10,-1) and right child (14,1), update map at 0

Map: {-2: 5, -1: 8, 0: 3, 1: 22}
Queue: [(25,2), (10,-1), (14,1)]

Why: Update bottom view for horizontal distance 0 and add children

Step 7: Pop (25,2), no children, update map at 2

Map: {-2: 5, -1: 8, 0: 3, 1: 22, 2: 25}
Queue: [(10,-1), (14,1)]

Why: Update bottom view for horizontal distance 2

Step 8: Pop (10,-1), no children, update map at -1

Map: {-2: 5, -1: 10, 0: 3, 1: 22, 2: 25}
Queue: [(14,1)]

Why: Update bottom view for horizontal distance -1 with lower node

Step 9: Pop (14,1), no children, update map at 1

Map: {-2: 5, -1: 10, 0: 3, 1: 14, 2: 25}
Queue: []

Why: Update bottom view for horizontal distance 1 with lower node

Result:

Bottom view nodes by horizontal distance:
-2: 5 -> -1: 10 -> 0: 3 -> 1: 14 -> 2: 25

Annotated Code

DSA C++

#include <iostream>
#include <map>
#include <queue>
using namespace std;

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

void bottomView(Node* root) {
    if (!root) return;
    map<int, int> hdNodeMap; // horizontal distance -> node data
    queue<pair<Node*, int>> q; // node and its horizontal distance
    q.push({root, 0});

    while (!q.empty()) {
        auto p = q.front(); q.pop();
        Node* curr = p.first;
        int hd = p.second;

        hdNodeMap[hd] = curr->data; // update bottom view for hd

        if (curr->left) q.push({curr->left, hd - 1});
        if (curr->right) q.push({curr->right, hd + 1});
    }

    for (auto& pair : hdNodeMap) {
        cout << pair.second << " ";
    }
    cout << endl;
}

int main() {
    Node* root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(5);
    root->left->right = new Node(3);
    root->right->right = new Node(25);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);

    bottomView(root);
    return 0;
}

q.push({root, 0});

Initialize queue with root at horizontal distance 0

auto p = q.front(); q.pop();

Process next node in BFS order

hdNodeMap[hd] = curr->data;

Update bottom view node for current horizontal distance

if (curr->left) q.push({curr->left, hd - 1});

Add left child with horizontal distance one less

if (curr->right) q.push({curr->right, hd + 1});

Add right child with horizontal distance one more

for (auto& pair : hdNodeMap) { cout << pair.second << " "; }

Print bottom view nodes in order of horizontal distance

Output

5 10 3 14 25 

Complexity Analysis

Time: O(n) because we visit each node once in BFS

Space: O(n) for the queue and map storing nodes and horizontal distances

vs Alternative: Compared to recursive vertical order traversal, BFS with map is simpler and efficient for bottom view

Edge Cases

Empty tree

Function returns without printing anything

DSA C++

if (!root) return;

Single node tree

Prints the single node as bottom view

DSA C++

q.push({root, 0});

Tree with all nodes on one side

Bottom view shows all nodes in a line

DSA C++

hdNodeMap[hd] = curr->data;

When to Use This Pattern

When asked to find nodes visible from bottom or horizontal view in a tree, use BFS with horizontal distances and update map to track bottom nodes.

Common Mistakes

Mistake: Not updating the map for horizontal distance on every node, so top nodes remain instead of bottom nodes
Fix: Always overwrite the map entry for horizontal distance during BFS to keep the bottom-most node

Summary

Finds the nodes visible when looking at a binary tree from the bottom.

Use when you need to see the lowest nodes at each horizontal distance in a tree.

The key is to track horizontal distances and update the node at each distance as you traverse level by level.