Bottom View of Binary Tree in DSA Typescript - 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 its horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

After traversal, extract nodes with max depth per horizontal distance

↓

Print bottom view from leftmost to rightmost horizontal distance

Traverse the tree level by level, track horizontal distances, update bottom nodes, then print from left to right.

Execution Sample

DSA Typescript

interface Node {
  val: number;
  left?: Node;
  right?: Node;
}

function bottomView(root: Node): number[] {
  if (!root) return [];

  const queue: [Node, number][] = [[root, 0]];
  const map = new Map<number, number>();

  while (queue.length > 0) {
    const [node, hd] = queue.shift()!;
    map.set(hd, node.val);

    if (node.left) {
      queue.push([node.left, hd - 1]);
    }
    if (node.right) {
      queue.push([node.right, hd + 1]);
    }
  }

  const sortedHd = Array.from(map.keys()).sort((a, b) => a - b);
  return sortedHd.map(hd => map.get(hd)!);
}

This code finds the bottom view of a binary tree by level order traversal and horizontal distance tracking.

Execution Table

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

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

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 14	Final
Queue	[ (20,0) ]	[]	[ (22,1) ]	[ (5,-2), (3,0) ]	[ (25,2), (10,1) ]	[]	[]
Bottom View Map	{}	{0:20}	{0:20, -1:8}	{0:20, -1:8, 1:22}	{0:3, -1:8, 1:22, -2:5}	{0:3, -1:8, 1:10, -2:5, 2:25}	{-2:5, -1:8, 0:3, 1:10, 2:25}

Key Moments - 3 Insights

Why does the bottom view map update the value at horizontal distance 0 from 20 to 3?

Because node 3 is visited later at the same horizontal distance 0 but at a lower level (deeper), it replaces the earlier node 20 in the bottom view map as shown in steps 7 and 11.

Why do we use a queue with horizontal distances instead of just nodes?

The queue stores nodes along with their horizontal distances to track their position relative to root. This helps decide which node is visible from bottom at each horizontal distance, as seen in the queue state column.

Why is the bottom view printed from leftmost to rightmost horizontal distance?

Because horizontal distances can be negative or positive, printing from smallest to largest hd ensures the bottom view is shown from left to right, as in the final bottom view map in step 15.

Visual Quiz - 3 Questions

Look at the execution table at step 11. What is the bottom view map value at horizontal distance 0?

A 8

B 20

C 3

D 10

💡 Hint

Check the 'Bottom View Map' column at step 11 in the execution table.

At which step does the horizontal distance 1 update from 22 to 10 in the bottom view map?

A Step 14

B Step 12

C Step 8

D Step 10

💡 Hint

Look at the 'Bottom View Map' column changes for hd=1 between steps 12 and 14.

If the node with value 3 had no right child, how would the queue state change at step 7?

A [ (22,1), (3,0) ]

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

C [ (22,1), (5,-2), (10,1) ]

D [ (22,1) ]

💡 Hint

At step 7, the right child of node 8 is enqueued; if missing, it won't be added.

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 from min hd to max hd
- Shows nodes visible from bottom view
- Uses BFS + hd mapping for solution

Full Transcript

The bottom view of a binary tree shows nodes visible when looking from the bottom. We start at the root with horizontal distance zero. Using a queue, we do a level order traversal. For each node, we record its value in a map keyed by horizontal distance. If a node appears later at the same horizontal distance but deeper, it replaces the earlier one. We enqueue left children with hd-1 and right children with hd+1. After visiting all nodes, we print the map values from the smallest to largest horizontal distance. This approach ensures we see the bottom-most nodes at each horizontal position.