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:

↓

Update map with node data at HD

↓

Enqueue right child with HD+1

↓

After traversal, extract map values sorted by HD

↓

Print bottom view nodes from left to right

Traverse the tree level by level, track horizontal distances, update bottom nodes at each horizontal distance, then print them sorted.

Execution Sample

DSA C

void bottomView(Node* root) {
  if (!root) return;
  map<int,int> hdNodeMap;
  queue<pair<Node*,int>> q;
  q.push({root,0});
  while (!q.empty()) {
    auto [node, hd] = q.front(); q.pop();
    hdNodeMap[hd] = node->data;
    if (node->left) q.push({node->left, hd-1});
    if (node->right) q.push({node->right, hd+1});
  }
  for (auto it : hdNodeMap) cout << it.second << " ";
}

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

Execution Table

Step	Operation	Node Visited	Horizontal Distance (HD)	Map Update (HD:Node)	Queue State	Bottom View Visual State
1	Start with 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	Enqueue right child	22	1	{0:20,-1:8,1:22}	[(5,-2),(3,0),(25,2)]	8 <- 20 -> 22
10	Dequeue node	5	-2	{0:20,-1:8,1:22,-2:5}	[(3,0),(25,2)]	5 <- 8 <- 20 -> 22
11	Dequeue node	3	0	{0:3,-1:8,1:22,-2:5}	[(25,2)]	5 <- 8 <- 3 -> 22
12	Dequeue node	25	2	{0:3,-1:8,1:22,-2:5,2:25}	[]	5 <- 8 <- 3 -> 22 -> 25
13	Traversal complete	N/A	N/A	{-2:5,-1:8,0:3,1:22,2:25}	[]	5 <- 8 <- 3 -> 22 -> 25

💡 Queue empty, traversal done, bottom view map finalized.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	Final
hdNodeMap	{}	{0:20}	{0:20,-1:8}	{0:20,-1:8,1:22}	{0:3,-1:8,1:22,-2:5}	{-2:5,-1:8,0:3,1:22,2:25}
Queue	[(20,0)]	[]	[(22,1)]	[(5,-2),(3,0)]	[(25,2)]	[]
Current Node	N/A	20	8	22	3	N/A

Key Moments - 3 Insights

Why does the map update the node value at the same horizontal distance instead of keeping the first?

Because bottom view shows the lowest node at each horizontal distance, the map updates with the latest node visited at that HD during level order traversal, as seen in steps 11 where HD 0 updates from 20 to 3.

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

HD starts at 0 for root; left child gets HD-1, right child HD+1. This helps track vertical alignment of nodes, as shown in the queue states in steps 3,4,6,7.

Why do we use a queue for traversal?

Queue enables level order traversal, ensuring nodes are processed top to bottom and left to right, which is essential to correctly update bottom view nodes, as shown by the queue changes in steps 2 to 12.

Visual Quiz - 3 Questions

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

A 20

B 3

C 8

D 22

💡 Hint

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

At which step does the horizontal distance -2 first get a node assigned in the map?

A Step 6

B Step 10

C Step 8

D Step 12

💡 Hint

Look for when HD -2 appears in the 'Map Update' column in the execution table.

If the node with value 3 had a left child with value 4, what would happen to the map at horizontal distance -1?

A HD -1 would update to 4

B HD -1 would remain 8

C HD -1 would update to 3

D HD -1 would update to 20

💡 Hint

Consider how left child nodes get HD-1 and map updates in the execution table.

Concept Snapshot

Bottom View of Binary Tree:
- Use level order traversal with a queue
- Track horizontal distance (HD) for each node
- Update map with node data at each HD (overwrite to keep bottom node)
- After traversal, print map values sorted by HD
- Shows nodes visible when viewed from bottom

Full Transcript

To find the bottom view of a binary tree, we start at the root with horizontal distance zero. We use a queue to traverse the tree level by level. For each node, we record its horizontal distance and update a map that stores the latest node at each horizontal distance. Left children have HD one less than their parent, right children one more. After processing all nodes, the map contains the bottom-most nodes for each horizontal distance. Printing these nodes in order of their horizontal distance gives the bottom view. This method ensures nodes lower in the tree overwrite those above at the same horizontal distance.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes that are visible when looking at the tree from below, ignoring nodes hidden behind others.

2. Step 2: Compare with other views

   Top, left, and right views show nodes from different angles, but bottom view specifically shows the lowest nodes at each horizontal distance.

3. Final Answer:

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

4. Quick Check:

   Bottom view = nodes visible from below [OK]

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

Common Mistakes:

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

2. Which data structure is commonly used to track nodes and their horizontal distances for bottom view calculation?

easy

A. Stack

B. Hash Map (Dictionary)

C. Linked List

D. Queue

Solution

1. Step 1: Identify the need for horizontal distance mapping

   To find the bottom view, we map each node's horizontal distance to its value, updating with the lowest node at that distance.

2. Step 2: Choose the suitable data structure

   A hash map (dictionary) stores horizontal distance as key and node value as value, allowing quick updates and lookups.

3. Final Answer:

   Hash Map (Dictionary) -> Option B

4. Quick Check:

   Use hash map to map horizontal distance to node [OK]

Hint: Use hash map to store horizontal distance and node value [OK]

Common Mistakes:

• Using stack which is LIFO and not suitable here
• Using queue alone without mapping distances
• Using linked list which is inefficient for lookups

3. What is the bottom view output of this binary tree?

        1
       / \
      2   3
       \   \
        4   5
         \   \
          6   7

Options show node values from left to right in bottom view.

medium

A. [2, 4, 6, 7]

B. [2, 4, 6, 3, 7]

C. [2, 4, 6, 5, 7]

D. [1, 2, 4, 6, 7]

Solution

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

   Assign horizontal distances: 1=0, 2=-1, 3=1, 4=0, 5=2, 6=1, 7=3. Bottom nodes at each distance are: -1:2, 0:4, 1:6, 2:5, 3:7.

2. Step 2: Collect bottom view nodes from left to right

   From leftmost (-1) to rightmost (3), nodes are 2, 4, 6, 5, 7.

3. Final Answer:

   [2, 4, 6, 5, 7] -> Option C

4. Quick Check:

   Bottom view nodes left to right = [2, 4, 6, 5, 7] [OK]

Hint: Track horizontal distances and pick last node at each [OK]

Common Mistakes:

• Including nodes not visible from bottom
• Confusing horizontal distances
• Listing nodes in wrong order

4. Identify the error in this C code snippet for bottom view calculation:

void bottomView(Node* root) {
    map hdNodeMap;
    queue> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        Node* node = p.first;
        int hd = p.second;
        if (hdNodeMap.find(hd) == hdNodeMap.end()) {
            hdNodeMap[hd] = node->data;
        }
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : hdNodeMap) {
        cout << it.second << " ";
    }
}

medium

A. Output loop should print keys instead of values

B. Queue is not initialized properly

C. Left and right child checks are reversed

D. Using map prevents updating bottom nodes at same horizontal distance

Solution

1. Step 1: Analyze map usage for horizontal distances

   The code inserts node data only if horizontal distance is not present, so it keeps the first node seen, which is top view behavior.

2. Step 2: Correct approach for bottom view

   For bottom view, update the map every time a node at the same horizontal distance is found, so the last node at that distance remains.

3. Final Answer:

   Using map prevents updating bottom nodes at same horizontal distance -> Option D

4. Quick Check:

   Bottom view needs updating map entries [OK]

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

Common Mistakes:

• Using if condition to insert only once (top view logic)
• Not updating map with lower nodes
• Confusing top and bottom view logic

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 show?

hard

A. Show the node that appears last in level order traversal at that horizontal distance

B. Show the node that appears first in level order traversal at that horizontal distance

C. Show the node with the smallest value at that horizontal distance

D. Show the node with the largest value 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 last node encountered in level order at that position.

2. Step 2: Use level order traversal order to decide

   Level order traversal visits nodes top to bottom, left to right. The last node at a horizontal distance overwrites previous ones in the map.

3. Final Answer:

   Show the node that appears last in level order traversal at that horizontal distance -> Option A

4. Quick Check:

   Bottom view picks last node at horizontal distance [OK]

Hint: Last node at horizontal distance in level order is bottom view node [OK]

Common Mistakes:

• Picking first node instead of last
• Choosing node by value instead of position
• Ignoring traversal order impact