Bottom View of Binary Tree in DSA Go - 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:

↓

Record node at horizontal distance

↓

Overwrite previous node at hd

↓

After traversal, extract nodes from min to max hd

↓

Print bottom view nodes in order

Traverse the tree level by level, track horizontal distances, overwrite nodes at each horizontal distance to get the bottom view.

Execution Sample

DSA Go

type Node struct {
  Val int
  Left, Right *Node
}

func BottomView(root *Node) []int {
  // BFS with horizontal distance tracking
}

This code performs a breadth-first traversal of the binary tree, tracking horizontal distances to find the bottom view nodes.

Execution Table

Step	Operation	Node Visited (Val, HD)	Map HD->Node	Queue State	Bottom View Visual
1	Start at root	(20, 0)	{0:20}	[(20,0)]	20
2	Dequeue node	(20, 0)	{0:20}	[]	20
3	Enqueue left child	(20, 0)	{0:20}	[(8,-1)]	20
4	Enqueue right child	(20, 0)	{0:20}	[(8,-1),(22,1)]	20
5	Dequeue node	(8, -1)	{0:20, -1:8}	[(22,1)]	8 -> 20
6	Enqueue left child	(8, -1)	{0:20, -1:8}	[(22,1),(5,-2)]	8 -> 20
7	Enqueue right child	(8, -1)	{0:20, -1:8}	[(22,1),(5,-2),(3,0)]	8 -> 20
8	Dequeue node	(22, 1)	{0:20, -1:8, 1:22}	[(5,-2),(3,0)]	8 -> 20 -> 22
9	No children to enqueue	(22, 1)	{0:20, -1:8, 1:22}	[(5,-2),(3,0)]	8 -> 20 -> 22
10	Dequeue node	(5, -2)	{0:20, -1:8, 1:22, -2:5}	[(3,0)]	5 -> 8 -> 20 -> 22
11	No children to enqueue	(5, -2)	{0:20, -1:8, 1:22, -2:5}	[(3,0)]	5 -> 8 -> 20 -> 22
12	Dequeue node	(3, 0)	{0:3, -1:8, 1:22, -2:5}	[]	5 -> 8 -> 3 -> 22
13	Enqueue right child	(3, 0)	{0:3, -1:8, 1:22, -2:5}	[(10,1)]	5 -> 8 -> 3 -> 22
14	Dequeue node	(10, 1)	{0:3, -1:8, 1:10, -2:5}	[]	5 -> 8 -> 3 -> 10
15	Enqueue right child	(10, 1)	{0:3, -1:8, 1:10, -2:5}	[(14,2)]	5 -> 8 -> 3 -> 10
16	Dequeue node	(14, 2)	{0:3, -1:8, 1:10, -2:5, 2:14}	[]	5 -> 8 -> 3 -> 10 -> 14
17	No children to enqueue	(14, 2)	{0:3, -1:8, 1:10, -2:5, 2:14}	[]	5 -> 8 -> 3 -> 10 -> 14
18	Traversal complete	N/A	{-2:5, -1:8, 0:3, 1:10, 2:14}	[]	5 -> 8 -> 3 -> 10 -> 14

💡 Queue empty, all nodes visited, bottom view map finalized.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 10	After Step 12	After Step 14	Final
Queue	[(20,0)]	[]	[(22,1)]	[(3,0)]	[]	[]	[]
Map HD->Node	{}	{0:20}	{0:20, -1:8}	{0:20, -1:8, 1:22, -2:5}	{0:3, -1:8, 1:22, -2:5}	{0:3, -1:8, 1:10, -2:5}	{-2:5, -1:8, 0:3, 1:10, 2:14}

Key Moments - 3 Insights

Why do we overwrite the node at a horizontal distance in the map during traversal?

Because the bottom view shows the lowest node at each horizontal distance, overwriting ensures the last node seen at that horizontal distance (lowest level) is recorded, as shown in steps 12 and 14 where node 3 and 10 overwrite previous nodes at hd 0 and 1.

Why do we use a queue and level order traversal instead of DFS?

Level order traversal visits nodes level by level, ensuring nodes at lower levels overwrite nodes at higher levels in the map. DFS might visit deeper nodes before shallower ones, causing incorrect bottom view, as the execution_table shows the queue processing order.

What does the horizontal distance represent and why is it important?

Horizontal distance (hd) measures how far left or right a node is from the root (hd=0). It helps group nodes vertically. The bottom view picks the lowest node at each hd, as tracked in the Map HD->Node column in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the node value recorded at horizontal distance 0?

A 3

B 8

C 20

D 10

💡 Hint

Check the Map HD->Node column at step 12 in the execution_table.

At which step does the horizontal distance -2 first get a node recorded?

A Step 5

B Step 14

C Step 10

D Step 18

💡 Hint

Look for when Map HD->Node first includes -2 in the execution_table.

If the node with value 3 had a left child with horizontal distance -1, how would the queue state change after step 12?

A Queue would only include (10,1)

B Queue would include (10,1) and (newNode,-1)

C Queue would include (10,1) and (newNode,0)

D Queue would include (14,2) and (newNode,-1)

💡 Hint

Check how children are enqueued with hd-1 and hd+1 in the execution_table steps 13 and 15.

Concept Snapshot

Bottom View of Binary Tree:
- Use level order traversal (BFS) with a queue.
- Track horizontal distance (hd) for each node.
- Overwrite map[hd] with current node to keep lowest node.
- After traversal, print nodes from min to max hd.
- Result shows nodes visible from bottom view.

Full Transcript

Bottom View of Binary Tree is found by traversing the tree level by level using a queue. Each node is assigned a horizontal distance from the root, starting at 0. When visiting nodes, we record or overwrite the node at that horizontal distance in a map. This ensures the bottom-most node at each horizontal distance is stored. After visiting all nodes, we print the nodes in order from the smallest to largest horizontal distance. The execution table shows each step: nodes visited, queue state, and the map of horizontal distances to nodes. Key moments clarify why overwriting is needed, why BFS is used, and the meaning of horizontal distance. The visual quiz tests understanding of map updates and queue changes. This method ensures the correct bottom view of the binary tree is obtained.