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

↓

Enqueue left child with hd-1

↓

Repeat until queue empty

↓

Extract bottom view from recorded nodes

↓

Print nodes from min hd to max hd

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

Execution Sample

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function bottomView(root) {
  // Implementation
}

This code defines a binary tree node and a function to find the bottom view of the tree.

Execution Table

Step	Operation	Node Visited (val, hd)	Queue State (val, hd)	Bottom View Map (hd: val)	Visual State
1	Start at root	(20, 0)	[(20,0)]	{}	20(0)
2	Dequeue node	(20, 0)	[]	{0:20}	20(0)
3	Enqueue left child	(20, 0)	[(8, -1)]	{0:20}	8(-1) <- 20(0)
4	Enqueue right child	(20, 0)	[(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	(8, -1)	[(22, 1), (5, -2)]	{0:20, -1:8}	5(-2) <- 8(-1) <- 20(0) -> 22(1)
7	Enqueue right child	(8, -1)	[(22, 1), (5, -2), (3, 0)]	{0:20, -1:8}	5(-2) <- 8(-1) <- 20(0) -> 22(1), 3(0)
8	Dequeue node	(22, 1)	[(5, -2), (3, 0)]	{0:20, -1:8, 1:22}	5(-2) <- 8(-1) <- 20(0) -> 22(1)
9	Enqueue right child	(22, 1)	[(5, -2), (3, 0), (25, 2)]	{0:20, -1:8, 1:22}	5(-2) <- 8(-1) <- 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) <- 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	(3, 0)	[(25, 2), (10, 1)]	{0:3, -1:8, 1:22, -2:5}	5(-2) <- 8(-1) <- 3(0) -> 22(1) -> 25(2), 10(1)
13	Dequeue node	(25, 2)	[(10, 1)]	{0:3, -1:8, 1:22, -2:5, 2:25}	5(-2) <- 8(-1) <- 3(0) -> 22(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	Queue empty	N/A	[]	{-2:5, -1:8, 0:3, 1:10, 2:25}	Final bottom view nodes
16	Print bottom view	N/A	N/A	5, 8, 3, 10, 25	5 -> 8 -> 3 -> 10 -> 25

💡 Queue is empty, all nodes processed, bottom view map complete

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, so it replaces 20 in the bottom view map as shown in steps 11 and 14.

Why do we use horizontal distance (hd) and how is it assigned?

Horizontal distance helps track the position of nodes relative to root: left child hd = parent hd - 1, right child hd = parent hd + 1. This is shown in the queue states where nodes have hd values like -1, 0, 1.

Why do we use a queue for traversal instead of recursion?

Queue enables level order traversal (breadth-first), ensuring nodes are processed top to bottom, left to right, which is necessary to correctly update the bottom view map as shown in the execution table.

Visual Quiz - 3 Questions

Look at the execution table, what is the bottom view map after step 8?

A {0:20, -1:8, 1:22}

B {0:3, -1:8, 1:22}

C {0:20, -1:8}

D {-2:5, -1:8, 0:3, 1:10, 2:25}

💡 Hint

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

At which step does the node with value 3 replace the previous node at horizontal distance 0 in the bottom view map?

A Step 5

B Step 11

C Step 2

D Step 14

💡 Hint

Look at the Bottom View Map changes in the execution table around steps 10 to 12.

If the node with value 10 was missing, how would the final bottom view change?

A It would remain the same

B Node 22 would remain at hd=1 in the bottom view

C Both B and C

D The bottom view would not include 10 at hd=1

💡 Hint

Check how bottom view map updates at hd=1 in steps 8, 11, and 14.

Concept Snapshot

Bottom View of Binary Tree:
- Use level order traversal with a queue
- Track horizontal distance (hd) for each node
- Update map with latest node at each hd
- After traversal, print nodes from min to max hd
- Shows nodes visible from bottom view
- Useful for visualizing tree structure horizontally

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 value at its horizontal distance in a map, replacing any previous value at that distance. We enqueue left and right children with hd-1 and hd+1 respectively. After processing all nodes, the map contains the bottom-most nodes at each horizontal distance. Printing these from the smallest to largest horizontal distance gives the bottom view. This method ensures nodes lower in the tree overwrite those above at the same horizontal distance. The execution table shows each step, queue state, and map updates, helping visualize how the bottom view is built.