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:

↓

Record node's value at its horizontal distance

↓

If left child exists: horizontal distance - 1

↓

If right child exists: horizontal distance + 1

↓

Continue until queue empty

↓

Collect last recorded nodes at each horizontal distance

↓

Output bottom view from leftmost to rightmost horizontal distance

Traverse the tree level by level, track horizontal distances, update bottom view nodes, then output nodes visible from bottom.

Execution Sample

DSA C#

class Node {
  public int val;
  public Node left, right;
  public Node(int v) { val = v; }
}

// Bottom view uses level order traversal with horizontal distances

This code defines a binary tree node and sets up for bottom view traversal using horizontal distances.

Execution Table

Step	Operation	Node Processed (val, HD)	Queue State (val, HD)	Bottom View Map (HD: val)	Visual State
1	Start with root	(20, 0)	[(20,0)]	{}	20(HD=0)
2	Dequeue node	(20, 0)	[]	{0:20}	20(HD=0)
3	Enqueue left child	(8, -1)	[(8,-1)]	{0:20}	8(HD=-1) <- 20(HD=0)
4	Enqueue right child	(22, 1)	[(8,-1), (22,1)]	{0:20}	8(HD=-1) <- 20(HD=0) -> 22(HD=1)
5	Dequeue node	(8, -1)	[(22,1)]	{0:20, -1:8}	8(HD=-1) <- 20(HD=0) -> 22(HD=1)
6	Enqueue left child	(5, -2)	[(22,1), (5,-2)]	{0:20, -1:8}	5(HD=-2) <- 8(HD=-1) <- 20(HD=0) -> 22(HD=1)
7	Enqueue right child	(3, 0)	[(22,1), (5,-2), (3,0)]	{0:20, -1:8}	5(HD=-2) <- 8(HD=-1) <- 20(HD=0) -> 22(HD=1)
8	Dequeue node	(22, 1)	[(5,-2), (3,0)]	{0:20, -1:8, 1:22}	5(HD=-2) <- 8(HD=-1) <- 20(HD=0) -> 22(HD=1)
9	Enqueue right child	(25, 2)	[(5,-2), (3,0), (25,2)]	{0:20, -1:8, 1:22}	5(HD=-2) <- 8(HD=-1) <- 20(HD=0) -> 22(HD=1) -> 25(HD=2)
10	Dequeue node	(5, -2)	[(3,0), (25,2)]	{0:20, -1:8, 1:22, -2:5}	5(HD=-2) <- 8(HD=-1) <- 20(HD=0) -> 22(HD=1) -> 25(HD=2)
11	No children to enqueue	(5, -2)	[(3,0), (25,2)]	{0:20, -1:8, 1:22, -2:5}	5(HD=-2) <- 8(HD=-1) <- 20(HD=0) -> 22(HD=1) -> 25(HD=2)
12	Dequeue node	(3, 0)	[(25,2)]	{0:3, -1:8, 1:22, -2:5}	5(HD=-2) <- 8(HD=-1) <- 3(HD=0) -> 22(HD=1) -> 25(HD=2)
13	Enqueue right child	(10, 1)	[(25,2), (10,1)]	{0:3, -1:8, 1:22, -2:5}	5(HD=-2) <- 8(HD=-1) <- 3(HD=0) -> 22(HD=1) -> 25(HD=2)
14	Dequeue node	(25, 2)	[(10,1)]	{0:3, -1:8, 1:22, -2:5, 2:25}	5(HD=-2) <- 8(HD=-1) <- 3(HD=0) -> 22(HD=1) -> 25(HD=2)
15	No children to enqueue	(25, 2)	[(10,1)]	{0:3, -1:8, 1:22, -2:5, 2:25}	5(HD=-2) <- 8(HD=-1) <- 3(HD=0) -> 22(HD=1) -> 25(HD=2)
16	Dequeue node	(10, 1)	[]	{0:3, -1:8, 1:10, -2:5, 2:25}	5(HD=-2) <- 8(HD=-1) <- 3(HD=0) -> 10(HD=1) -> 25(HD=2)
17	No children to enqueue	(10, 1)	[]	{0:3, -1:8, 1:10, -2:5, 2:25}	5(HD=-2) <- 8(HD=-1) <- 3(HD=0) -> 10(HD=1) -> 25(HD=2)
18	Queue empty, end traversal	-	[]	{-2:5, -1:8, 0:3, 1:10, 2:25}	Final bottom view nodes

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

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
Queue	[(20,0)]	[]	[(8,-1)]	[(8,-1), (22,1)]	[(22,1)]	[(22,1), (5,-2)]	[(22,1), (5,-2), (3,0)]	[(5,-2), (3,0)]	[(5,-2), (3,0), (25,2)]	[(3,0), (25,2)]	[(25,2)]	[]
Bottom View Map	{}	{0:20}	{0:20}	{0:20}	{0:20, -1:8}	{0:20, -1:8}	{0:20, -1:8}	{0:20, -1:8, 1:22}	{0:20, -1:8, 1:22}	{0:20, -1:8, 1:22, -2:5}	{0:3, -1:8, 1:22, -2:5}	{-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 appears later at horizontal distance 0 during level order traversal, it overwrites the previous value 20 in the bottom view map, as shown in execution_table step 12.

Why do we use horizontal distances and not just node values to determine the bottom view?

Horizontal distances help identify nodes aligned vertically. The bottom view shows the lowest node at each horizontal distance, so tracking HD is essential, as seen in the concept_flow and execution_table.

What happens if a node has no children during traversal?

No new nodes are enqueued, and traversal continues with remaining nodes in the queue, as shown in steps 11, 15, and 17 where no children are added.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the bottom view map's value at horizontal distance 0?

A 20

B 3

C 8

D 10

💡 Hint

Check the Bottom View Map column at step 12 in the execution_table.

At which step does the queue become empty, ending the traversal?

A Step 16

B Step 17

C Step 18

D Step 15

💡 Hint

Look for the step where Queue State is empty and exit_note in execution_table.

If the node with value 3 had a left child at horizontal distance -1, how would the bottom view map change after processing it?

A It would update HD -1 with the new child's value

B It would update HD 0 with the new child's value

C It would not change the bottom view map

D It would remove HD -1 from the map

💡 Hint

Refer to how children nodes update bottom view map at their horizontal distances in execution_table steps 6 and 7.

Concept Snapshot

Bottom View of Binary Tree:
- Traverse tree level order with a queue
- Track horizontal distance (HD) for each node
- Update map with node value at HD (overwrites previous)
- After traversal, output nodes from min to max HD
- Shows nodes visible from bottom
- Uses BFS + HD mapping

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 node with horizontal distance zero. Using a queue, we perform a level order traversal. For each node, we record its value at its horizontal distance in a map, overwriting any previous value at that distance. We enqueue left and right children with horizontal distances decremented and incremented respectively. After processing all nodes, the map contains the bottom view nodes. The output is the values from the smallest to largest horizontal distance. This method ensures the lowest nodes at each vertical line are captured.

Practice

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

easy

A. The nodes visible when the tree is viewed from the right side

B. The nodes visible when the tree is viewed from the top

C. The nodes visible when the tree is viewed from the left side

D. The nodes visible when the tree is viewed from the bottom

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:

   The nodes visible when the tree is viewed from the bottom -> Option D

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 C# data structure is best suited to store nodes by their horizontal distance when computing the bottom view of a binary tree?

easy

A. Dictionary

B. List<int>

C. Stack<int>

D. Queue<int>

Solution

1. Step 1: Identify the need to map horizontal distance to node value

   We need a structure to store nodes keyed by their horizontal distance for quick updates and lookups.

2. Step 2: Choose the appropriate data structure

   A Dictionary allows mapping horizontal distance (int) to node value (int) efficiently.

3. Final Answer:

   Dictionary<int, int> -> Option A

4. Quick Check:

   Use Dictionary for horizontal distance mapping [OK]

Hint: Use Dictionary to map horizontal distance to node value [OK]

Common Mistakes:

• Using List which doesn't map keys to values
• Using Stack or Queue which are not key-value stores
• Confusing data structure roles

3. Consider the following binary tree:

        20
       /  \
     8     22
    / \      \
   5   3      25
      /  \
     10   14

What is the bottom view of this tree?

medium

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

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

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

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

Solution

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

   Assign horizontal distances (HD) starting from root (20) at HD=0: - 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(-1), 14(1) For each HD, the bottom-most node is: HD -2: 5 HD -1: 10 (overwrites 8) HD 0: 3 (overwrites 20) HD 1: 14 (overwrites 22) HD 2: 25

2. Step 2: Collect bottom view nodes in order of HD

   Order HD from left to right: -2, -1, 0, 1, 2 Bottom view nodes: [5, 10, 3, 14, 25]

3. Final Answer:

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

4. Quick Check:

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

Hint: Track horizontal distance and overwrite with lower nodes [OK]

Common Mistakes:

• Not updating nodes at same horizontal distance
• Confusing top view with bottom view
• Ignoring horizontal distance ordering

4. The following C# code attempts to compute the bottom view of a binary tree but has a bug. What is the error?

void BottomView(Node root) {
    if (root == null) return;
    var map = new Dictionary();
    var queue = new Queue<(Node node, int hd)>();
    queue.Enqueue((root, 0));
    while (queue.Count > 0) {
        var (node, hd) = queue.Dequeue();
        if (!map.ContainsKey(hd)) {
            map[hd] = node.data;
        }
        if (node.left != null) queue.Enqueue((node.left, hd - 1));
        if (node.right != null) queue.Enqueue((node.right, hd + 1));
    }
    foreach (var key in map.Keys.OrderBy(k => k)) {
        Console.Write(map[key] + " ");
    }
}

medium

A. It does not enqueue the root node

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

C. It uses a queue instead of a stack

D. It does not order the keys before printing

Solution

1. Step 1: Analyze how nodes are stored in the map

   The code adds node data to map only if the horizontal distance key is not present, so it keeps the first node encountered at that HD.

2. Step 2: Understand bottom view requires last node at each HD

   Bottom view needs the lowest node at each HD, so the map should update the value every time a node at the same HD is found, not only the first.

3. Final Answer:

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

4. Quick Check:

   Bottom view needs last node per HD, not first [OK]

Hint: Update map value for each node at HD to get bottom view [OK]

Common Mistakes:

• Using if (!map.ContainsKey) instead of always updating
• Ignoring horizontal distance updates
• Not ordering keys before printing (though code does)

5. You are given a binary tree where multiple nodes share the same horizontal distance and depth. How would you modify the bottom view algorithm to always show the node with the greatest depth at each horizontal distance?

hard

A. Store pairs of (node value, depth) in the map and update only if new node's depth is greater

B. Store only node values and update map only if node value is greater

C. Use a stack instead of a queue to traverse nodes

D. Ignore depth and just print nodes in level order

Solution

1. Step 1: Recognize the need to track depth with node values

   To ensure the bottom view shows the node with greatest depth at each horizontal distance, we must store depth along with node value.

2. Step 2: Update map only if new node's depth is greater

   When visiting a node, compare its depth with stored depth for that horizontal distance; update only if current node is deeper.

3. Final Answer:

   Store pairs of (node value, depth) in the map and update only if new node's depth is greater -> Option A

4. Quick Check:

   Track depth and update map for deeper nodes [OK]

Hint: Keep depth info and update map only if deeper node found [OK]

Common Mistakes:

• Ignoring depth and overwriting incorrectly
• Comparing node values instead of depths
• Changing traversal order without depth tracking