Bottom View of Binary Tree in DSA C++ - Execution Trace

Concept Flow - Bottom View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for level order traversal

↓

For each node dequeued:

↓

Update map with node at HD

↓

Enqueue right child with HD+1

↓

Repeat until queue empty

↓

Extract bottom view from map sorted by HD

↓

Print bottom view nodes left to right

Traverse the tree level by level, track horizontal distances, update bottom-most node at each horizontal distance, then print nodes from leftmost to rightmost horizontal distance.

Execution Sample

DSA C++

struct Node {
  int data;
  Node* left;
  Node* right;
};

// Bottom view function uses level order traversal with HD tracking

This code traverses the binary tree level-wise, tracks horizontal distances, and updates the bottom view nodes.

Execution Table

Step	Operation	Node Visited (data)	Horizontal Distance (HD)	Map State (HD:Node)	Queue State (Node, HD)	Visual State
1	Start at root	20	0	{0:20}	[(20,0)]	20(HD=0)
2	Dequeue node	20	0	{0:20}	[]	20(HD=0)
3	Enqueue left child	8	-1	{0:20}	[(8,-1)]	20(0) -> 8(-1)
4	Enqueue right child	22	1	{0:20}	[(8,-1),(22,1)]	8(-1) <- 20(0) -> 22(1)
5	Dequeue node	8	-1	{0:20, -1:8}	[(22,1)]	8(-1) -> 20(0) -> 22(1)
6	Enqueue left child	5	-2	{0:20, -1:8}	[(22,1),(5,-2)]	5(-2) -> 8(-1) -> 20(0) -> 22(1)
7	Enqueue right child	3	0	{0:20, -1:8}	[(22,1),(5,-2),(3,0)]	5(-2) -> 8(-1) -> 3(0) -> 20(0) -> 22(1)
8	Dequeue node	22	1	{0:20, -1:8, 1:22}	[(5,-2),(3,0)]	5(-2) -> 8(-1) -> 3(0) -> 20(0) -> 22(1)
9	Enqueue right child	25	2	{0:20, -1:8, 1:22}	[(5,-2),(3,0),(25,2)]	5(-2) -> 8(-1) -> 3(0) -> 20(0) -> 22(1) -> 25(2)
10	Dequeue node	5	-2	{0:20, -1:8, 1:22, -2:5}	[(3,0),(25,2)]	5(-2) -> 8(-1) -> 3(0) -> 20(0) -> 22(1) -> 25(2)
11	Dequeue node	3	0	{0:3, -1:8, 1:22, -2:5}	[(25,2)]	5(-2) -> 8(-1) -> 3(0) -> 22(1) -> 25(2)
12	Dequeue node	25	2	{0:3, -1:8, 1:22, -2:5, 2:25}	[]	5(-2) -> 8(-1) -> 3(0) -> 22(1) -> 25(2)
13	Queue empty	-	-	{-2:5, -1:8, 0:3, 1:22, 2:25}	[]	Bottom view nodes: 5 -> 8 -> 3 -> 22 -> 25

💡 Queue is empty, traversal complete, bottom view map finalized.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	Final
Queue	[(20,0)]	[]	[(22,1)]	[(5,-2),(3,0)]	[(25,2)]	[]
Map (HD:Node)	{}	{0:20}	{0:20, -1:8}	{0:20, -1:8, 1:22}	{0:3, -1:8, 1:22, -2:5}	{-2:5, -1:8, 0:3, 1:22, 2:25}
Current Node	20	8	22	3	25	-

Key Moments - 3 Insights

Why does the map update the node at horizontal distance 0 from 20 to 3 at step 11?

Because node 3 is lower (visited later in level order) at the same horizontal distance 0, it replaces 20 in the map as the bottom view node at HD 0 (see execution_table step 11).

Why do we use horizontal distance (HD) to track nodes?

HD helps identify vertical alignment of nodes. Nodes with the same HD are in the same vertical line. The bottom view shows the lowest node at each HD (see concept_flow and execution_table).

Why do we use a queue for traversal?

Queue enables level order traversal, visiting nodes top to bottom and left to right, ensuring bottom-most nodes overwrite earlier ones in the map (see execution_table steps showing queue state).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what nodes are currently in the queue?

A [(22,1), (5,-2), (3,0)]

B [(8,-1), (22,1), (5,-2)]

C [(5,-2), (3,0)]

D [(3,0), (25,2)]

💡 Hint

Check the 'Queue State' column at step 7 in the execution_table.

At which step does the map first get updated with horizontal distance -2?

A Step 6

B Step 5

C Step 10

D Step 9

💡 Hint

Look at the 'Map State' column for when HD -2 appears in the execution_table.

If the node with data 3 was not present, what would be the bottom view node at HD 0 after traversal?

A 22

B 20

C 8

D 5

💡 Hint

Refer to the map updates in execution_table steps 11 and 12 where node 3 replaces 20 at HD 0.

Concept Snapshot

Bottom View of Binary Tree:
- Traverse tree level order with queue
- Track horizontal distance (HD) for each node
- Update map with latest node at each HD
- After traversal, print nodes sorted by HD
- Shows lowest visible nodes from bottom
- Uses map and queue for O(n) time

Full Transcript

The bottom view of a binary tree shows the nodes visible when the tree is viewed from the bottom. We start at the root with horizontal distance zero. Using a queue, we traverse the tree level by level. For each node, we record its horizontal distance. We update a map to keep the latest node at each horizontal distance, which represents the bottom-most node. We enqueue left and right children with horizontal distances decremented and incremented respectively. After the queue is empty, the map contains the bottom view nodes. We print these nodes sorted by their horizontal distance from left to right. This approach ensures we see the lowest nodes at each vertical line of the tree.