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.

Practice

1. What does the bottom view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the right side

B. Nodes visible when the tree is viewed from the top

C. Nodes visible when the tree is viewed from the bottom

D. Nodes visible when the tree is viewed from the left side

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes visible when looking at the tree from below, meaning the lowest nodes at each horizontal distance.

2. Step 2: Compare with other views

   Top view shows nodes from above, left and right views show nodes from sides, so bottom view is unique for bottom perspective.

3. Final Answer:

   Nodes visible when the tree is viewed from the bottom -> Option C

4. Quick Check:

   Bottom view = nodes visible from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal distance [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking bottom view shows all leaf nodes
• Mixing bottom view with side views

2. Which of the following JavaScript code snippets correctly initializes a Map to store horizontal distances and nodes for bottom view?

easy

A. const map = new Map();

B. const map = {};

C. const map = new Array();

D. const map = new Set();

Solution

1. Step 1: Identify suitable data structure for key-value pairs

   Map is ideal for storing horizontal distance as key and node data as value with easy insertion and retrieval.

2. Step 2: Check other options

   Object ({}) can be used but Map is preferred for ordered keys and better methods; Array and Set are not suitable for key-value pairs.

3. Final Answer:

   const map = new Map(); -> Option A

4. Quick Check:

   Use Map for horizontal distance mapping [OK]

Hint: Use Map() for key-value storage in bottom view [OK]

Common Mistakes:

• Using Array instead of Map for key-value pairs
• Using Set which stores only unique values, not key-value
• Using plain object without considering key types

3. Consider the following binary tree and code snippet to print its bottom view:

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

const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

// Bottom view logic omitted for brevity
// Assume correct implementation

// Output bottom view nodes in order of horizontal distance
// What is the bottom view output?

medium

A. [5, 8, 3, 14, 25]

B. [5, 10, 3, 14, 25]

C. [5, 10, 3, 22, 25]

D. [8, 10, 3, 14, 25]

Solution

1. Step 1: Assign horizontal distances and track bottom nodes

   Assign horizontal distances: 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(-1), 14(1). Bottom view keeps last node at each horizontal distance.

2. Step 2: Determine bottom nodes at each horizontal distance

   At -2: 5; at -1: 10 (overwrites 8); at 0: 3 (overwrites 20); at 1: 14 (overwrites 22); at 2: 25.

3. Final Answer:

   [5, 10, 3, 14, 25] -> Option B

4. Quick Check:

   Bottom view nodes = [5,10,3,14,25] [OK]

Hint: Track last node at each horizontal distance [OK]

Common Mistakes:

• Using first node instead of last at horizontal distance
• Mixing horizontal distances incorrectly
• Ignoring overwriting nodes at same horizontal distance

4. The following code attempts to print the bottom view of a binary tree but produces incorrect output. What is the main issue?

function bottomView(root) {
  const map = new Map();
  const queue = [];
  queue.push({ node: root, hd: 0 });

  while (queue.length > 0) {
    const { node, hd } = queue.shift();
    if (!map.has(hd)) {
      map.set(hd, node.data);
    }
    if (node.left) queue.push({ node: node.left, hd: hd - 1 });
    if (node.right) queue.push({ node: node.right, hd: hd + 1 });
  }

  return Array.from(map.values());
}

medium

A. It stores only the first node at each horizontal distance, not the bottom-most

B. It uses shift() which is inefficient for queue

C. It does not handle null root input

D. It uses Map instead of Object for storage

Solution

1. Step 1: Analyze map update condition

   The code sets map value only if horizontal distance key is not present, so it keeps first node encountered at that hd.

2. Step 2: Understand bottom view requirement

   Bottom view requires last node at each horizontal distance (lowest level), so map should update value every time a node at same hd is found.

3. Final Answer:

   It stores only the first node at each horizontal distance, not the bottom-most -> Option A

4. Quick Check:

   Bottom view needs last node per hd, code keeps first [OK]

Hint: Update map value for every node at horizontal distance [OK]

Common Mistakes:

• Not updating map on repeated horizontal distances
• Confusing top view logic with bottom view
• Ignoring queue inefficiency but that doesn't affect correctness

5. Given a binary tree where multiple nodes share the same horizontal distance and level, how should the bottom view algorithm decide which node to display?

hard

A. Display the node with the smallest value at that horizontal distance

B. Display the leftmost node at that horizontal distance and level

C. Display the rightmost node at that horizontal distance and level

D. Display the node encountered last in level order traversal at that horizontal distance

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, bottom view shows the one visible from bottom, which is the one encountered last in level order traversal.

2. Step 2: Reason about traversal order

   Level order traversal processes nodes left to right at each level, so last encountered node at hd and level overwrites previous.

3. Final Answer:

   Display the node encountered last in level order traversal at that horizontal distance -> Option D

4. Quick Check:

   Bottom view uses last node in level order per hd [OK]

Hint: Use last node in level order traversal for bottom view [OK]

Common Mistakes:

• Choosing leftmost or rightmost arbitrarily
• Choosing node by value instead of position
• Ignoring traversal order impact