Bottom view of a Binary Tree
What do you see from the bottom?
Imagine looking up at the tree from below. Nodes aligned on the same vertical line overlap — only the lowest one is visible. This algorithm uses BFS to assign each node a "vertical position" and keeps overwriting the map so the last (deepest) node at each position wins.
How vertical positions work
The root is at vertical position 0. Going left subtracts 1 (line - 1);
going right adds 1 (line + 1). Nodes on the same vertical position form a column —
like floors of a building seen from below.
Why BFS + map = bottom view
BFS visits nodes level by level (top to bottom). Each time a node is visited at a given vertical line, its value overwrites the previous one in the map. Since deeper nodes are visited later, the final value stored for each line is the bottom-most node — exactly the bottom view.
The tree and its vertical lines
The main() function builds this tree. Each node is labeled with its data value and
assigned a vertical position. The dashed vertical guides show the columns — nodes in the same
column will compete for visibility. Only the bottom-most node in each column survives.
Note: nodes 10 (left subtree) and 9 both sit at line 0, and node 1 is also at line 0. They will compete — the deepest one wins.
Initialize — push root into the queue
The queue starts with the root node paired with its vertical position 0.
The map mpp is empty. Everything is set for BFS to begin.
1if (root == NULL) return ans;
2map<int, int> mpp;
3queue<pairint >> q;
4q.push({root, 0}); // root at vertical position 0Process node 1 (line 0) — first map entry
Pop (1, 0) from the queue. The map has no entry for line 0 yet, so this is a new insertion.
Then push both children: (2, -1) and (3, +1).
| line | value | action |
|---|---|---|
| 0 | 1 | NEW |
1while (!q.empty()) {
2 auto it = q.front(); q.pop();
3 Node* node = it.first; // node = 1
4 int line = it.second; // line = 0
5 mpp[line] = node->data; // mpp[0] = 1 (new entry)
6
7 if (node->left) q.push({node->left, line - 1}); // push (2, -1)
8 if (node->right) q.push({node->right, line + 1}); // push (3, +1)
9}mpp[0] = 1 → first node at vertical position 0
Process node 2 (line -1) — two new entries
Pop (2, -1). Line -1 is empty → new entry with value 2.
Push children: (4, -2) and (10, 0) — note that node 10 also lands on line 0.
| line | value | action |
|---|---|---|
| -1 | 2 | NEW |
| 0 | 1 | — |
1 Node* node = it.first; // node = 2
2 int line = it.second; // line = -1
3 mpp[line] = node->data; // mpp[-1] = 2 (new entry)
4
5 if (node->left) q.push({node->left, line - 1}); // push (4, -2)
6 if (node->right) q.push({node->right, line + 1}); // push (10, 0) ← same line as root!mpp[-1] = 2. Node 10 queued at line 0 — it will compete with node 1 later.
Process node 3 (line +1) — new entry
Pop (3, +1). Line +1 is empty → new entry with value 3.
Push children: (9, 0) — another node at line 0 — and (10, +2).
| line | value | action |
|---|---|---|
| -1 | 2 | — |
| 0 | 1 | — |
| +1 | 3 | NEW |
mpp[+1] = 3. Two more nodes queued at line 0 — the battle for line 0 heats up.
Process node 4 (line -2) — new entry
Pop (4, -2). Line -2 is empty → new entry with value 4.
Push child: (5, -1) — node 5 is at line -1, where node 2 currently sits.
| line | value | action |
|---|---|---|
| -2 | 4 | NEW |
| -1 | 2 | — |
| 0 | 1 | — |
| +1 | 3 | — |
mpp[-2] = 4. Node 5 queued at line -1 — will it replace node 2?
Process node 10 (line 0) — first overwrite!
Pop (10, 0). Line 0 already has value 1 (from the root), but BFS overwrites it
unconditionally: mpp[0] = 10. The root's value at line 0 is now gone — replaced by
this deeper node. Node 10 is a leaf (left subtree version), so no children are pushed.
| line | value | action |
|---|---|---|
| -2 | 4 | — |
| -1 | 2 | — |
| 0 | 10 (was 1) | OVERWRITE |
| +1 | 3 | — |
1 Node* node = it.first; // node = 10
2 int line = it.second; // line = 0
3 mpp[line] = node->data; // mpp[0] = 10 ← overwrites 1!
4
5 // node 10 is a leaf — no children to pushmpp[0]: 1 → 10. The root is no longer the bottom-most node at line 0.
Process node 9 (line 0) — second overwrite!
Pop (9, 0). Line 0 just got overwritten to 10, and now it's overwritten again:
mpp[0] = 9. This is the key insight — BFS processes nodes level by level, so deeper nodes
always come later and overwrite shallower ones. Node 9 is also a leaf.
| line | value | action |
|---|---|---|
| -2 | 4 | — |
| -1 | 2 | — |
| 0 | 9 (was 10) | OVERWRITE |
| +1 | 3 | — |
mpp[0]: 10 → 9. But wait — there's still node 6 deeper down at line 0...
Process node 10 (line +2) — new entry
Pop (10, +2). Line +2 is empty → new entry. This node (right subtree's right child) is a leaf,
so no children are pushed.
| line | value | action |
|---|---|---|
| -2 | 4 | — |
| -1 | 2 | — |
| 0 | 9 | — |
| +1 | 3 | — |
| +2 | 10 | NEW |
mpp[+2] = 10. Only one node left in the queue.
Process node 5 (line -1) — overwrite node 2
Pop (5, -1). Line -1 currently has value 2, but node 5 is deeper (it's below node 4).
Overwrite: mpp[-1] = 5. Push child: (6, 0) — one more contender for line 0!
| line | value | action |
|---|---|---|
| -2 | 4 | — |
| -1 | 5 (was 2) | OVERWRITE |
| 0 | 9 | — |
| +1 | 3 | — |
| +2 | 10 | — |
mpp[-1]: 2 → 5. Node 5 is deeper than node 2. One more node in queue...
Process node 6 (line 0) — the final overwrite!
Pop (6, 0). Line 0 has been overwritten twice already (1 → 10 → 9), and now node 6 — the deepest
node at line 0 — takes the crown: mpp[0] = 6. This is why the algorithm works:
BFS guarantees that the last node visited at any vertical position is the bottom-most one. The queue is now empty.
| line | value | action |
|---|---|---|
| -2 | 4 | — |
| -1 | 5 | — |
| 0 | 6 (was 9) | OVERWRITE |
| +1 | 3 | — |
| +2 | 10 | — |
mpp[0]: 9 → 6. Node 6 is the deepest at line 0. BFS is done.
Extract from map → result vector
The BFS loop is done. The map now holds the bottom-most node for each vertical position. Since
std::map keeps keys sorted, iterating from -2 to +2 gives the
bottom view in left-to-right order. The values are transferred to the result vector.
1// map is sorted by key: -2, -1, 0, +1, +2
2for (auto it : mpp) {
3 ans.push_back(it.second); // extract values in sorted key order
4}
5return ans; // {4, 5, 6, 3, 10}The bottom view is 4 5 6 3 10
The algorithm visited all 9 nodes via BFS, assigning each a vertical position. Five vertical lines
were discovered (-2, -1, 0, +1, +2). Line 0 saw the most action — four nodes competed for it, and
node 6 (the deepest) won. The std::map kept everything sorted by key, so the final
iteration produced the bottom view in left-to-right order.
| Vertical Line | Nodes at this line | Overwrites | Bottom View Winner |
|---|---|---|---|
| -2 | 4 | 0 (new) | 4 |
| -1 | 2, 5 | 1 (2→5) | 5 |
| 0 | 1, 10, 9, 6 | 3 (1→10→9→6) | 6 |
| +1 | 3 | 0 (new) | 3 |
| +2 | 10 | 0 (new) | 10 |