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

↓

Overwrite previous node at hd

↓

After traversal, extract nodes from min to max hd

↓

Print bottom view nodes in order

Traverse the tree level by level, track horizontal distances, overwrite nodes at each horizontal distance to get the bottom view.

Execution Sample

DSA Go

type Node struct {
  Val int
  Left, Right *Node
}

func BottomView(root *Node) []int {
  // BFS with horizontal distance tracking
}

This code performs a breadth-first traversal of the binary tree, tracking horizontal distances to find the bottom view nodes.

Execution Table

Step	Operation	Node Visited (Val, HD)	Map HD->Node	Queue State	Bottom View Visual
1	Start at 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	No children to enqueue	(22, 1)	{0:20, -1:8, 1:22}	[(5,-2),(3,0)]	8 -> 20 -> 22
10	Dequeue node	(5, -2)	{0:20, -1:8, 1:22, -2:5}	[(3,0)]	5 -> 8 -> 20 -> 22
11	No children to enqueue	(5, -2)	{0:20, -1:8, 1:22, -2:5}	[(3,0)]	5 -> 8 -> 20 -> 22
12	Dequeue node	(3, 0)	{0:3, -1:8, 1:22, -2:5}	[]	5 -> 8 -> 3 -> 22
13	Enqueue right child	(3, 0)	{0:3, -1:8, 1:22, -2:5}	[(10,1)]	5 -> 8 -> 3 -> 22
14	Dequeue node	(10, 1)	{0:3, -1:8, 1:10, -2:5}	[]	5 -> 8 -> 3 -> 10
15	Enqueue right child	(10, 1)	{0:3, -1:8, 1:10, -2:5}	[(14,2)]	5 -> 8 -> 3 -> 10
16	Dequeue node	(14, 2)	{0:3, -1:8, 1:10, -2:5, 2:14}	[]	5 -> 8 -> 3 -> 10 -> 14
17	No children to enqueue	(14, 2)	{0:3, -1:8, 1:10, -2:5, 2:14}	[]	5 -> 8 -> 3 -> 10 -> 14
18	Traversal complete	N/A	{-2:5, -1:8, 0:3, 1:10, 2:14}	[]	5 -> 8 -> 3 -> 10 -> 14

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

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 10	After Step 12	After Step 14	Final
Queue	[(20,0)]	[]	[(22,1)]	[(3,0)]	[]	[]	[]
Map HD->Node	{}	{0:20}	{0:20, -1:8}	{0:20, -1:8, 1:22, -2:5}	{0:3, -1:8, 1:22, -2:5}	{0:3, -1:8, 1:10, -2:5}	{-2:5, -1:8, 0:3, 1:10, 2:14}

Key Moments - 3 Insights

Why do we overwrite the node at a horizontal distance in the map during traversal?

Because the bottom view shows the lowest node at each horizontal distance, overwriting ensures the last node seen at that horizontal distance (lowest level) is recorded, as shown in steps 12 and 14 where node 3 and 10 overwrite previous nodes at hd 0 and 1.

Why do we use a queue and level order traversal instead of DFS?

Level order traversal visits nodes level by level, ensuring nodes at lower levels overwrite nodes at higher levels in the map. DFS might visit deeper nodes before shallower ones, causing incorrect bottom view, as the execution_table shows the queue processing order.

What does the horizontal distance represent and why is it important?

Horizontal distance (hd) measures how far left or right a node is from the root (hd=0). It helps group nodes vertically. The bottom view picks the lowest node at each hd, as tracked in the Map HD->Node column in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the node value recorded at horizontal distance 0?

A 3

B 8

C 20

D 10

💡 Hint

Check the Map HD->Node column at step 12 in the execution_table.

At which step does the horizontal distance -2 first get a node recorded?

A Step 5

B Step 14

C Step 10

D Step 18

💡 Hint

Look for when Map HD->Node first includes -2 in the execution_table.

If the node with value 3 had a left child with horizontal distance -1, how would the queue state change after step 12?

A Queue would only include (10,1)

B Queue would include (10,1) and (newNode,-1)

C Queue would include (10,1) and (newNode,0)

D Queue would include (14,2) and (newNode,-1)

💡 Hint

Check how children are enqueued with hd-1 and hd+1 in the execution_table steps 13 and 15.

Concept Snapshot

Bottom View of Binary Tree:
- Use level order traversal (BFS) with a queue.
- Track horizontal distance (hd) for each node.
- Overwrite map[hd] with current node to keep lowest node.
- After traversal, print nodes from min to max hd.
- Result shows nodes visible from bottom view.

Full Transcript

Bottom View of Binary Tree is found by traversing the tree level by level using a queue. Each node is assigned a horizontal distance from the root, starting at 0. When visiting nodes, we record or overwrite the node at that horizontal distance in a map. This ensures the bottom-most node at each horizontal distance is stored. After visiting all nodes, we print the nodes in order from the smallest to largest horizontal distance. The execution table shows each step: nodes visited, queue state, and the map of horizontal distances to nodes. Key moments clarify why overwriting is needed, why BFS is used, and the meaning of horizontal distance. The visual quiz tests understanding of map updates and queue changes. This method ensures the correct bottom view of the binary tree is obtained.

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 view shows nodes from above, left view from left side, right view from right side. Bottom view is unique for the bottom perspective.

3. Final Answer:

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

4. Quick Check:

   Bottom view = Nodes visible from bottom [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 data structure is commonly used to track nodes and their horizontal distances when computing the bottom view of a binary tree in Go?

easy

A. Stack

B. Queue

C. Map (dictionary)

D. Slice

Solution

1. Step 1: Identify the need to map horizontal distances

   To find bottom view, we track nodes by their horizontal distance from root, so we need a structure to map distance to node value.

2. Step 2: Choose the correct data structure

   A map (dictionary) stores key-value pairs, perfect for horizontal distance as key and node value as value.

3. Final Answer:

   Map (dictionary) -> Option C

4. Quick Check:

   Use map to store horizontal distance -> node [OK]

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

Common Mistakes:

• Using stack which is LIFO, not suitable here
• Using queue only for traversal, not for mapping
• Using slice without keys for horizontal distance

3. Given the binary tree below, what is the bottom view output?

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

medium

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

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

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

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

Solution

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

   Assign horizontal distances (HD) starting from root (20) as 0. Left child decreases HD by 1, right child increases by 1. - 20 (HD=0) - 8 (HD=-1), 22 (HD=1) - 5 (HD=-2), 3 (HD=0), 25 (HD=2) - 10 (HD=-1), 14 (HD=1)

2. Step 2: Determine bottom view nodes by last node at each HD

   At HD=-2: 5 HD=-1: 10 (overwrites 8) HD=0: 3 (overwrites 20) HD=1: 14 (overwrites 22) HD=2: 25 Bottom view = [5, 10, 3, 14, 25]

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Taking first node at HD instead of last
• Mixing horizontal distances
• Ignoring nodes on right side

4. Consider this Go code snippet for bottom view. What is the error?

func bottomView(root *Node) []int {
    if root == nil {
        return nil
    }
    queue := []*Node{root}
    hdMap := make(map[int]int)
    hd := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        hdMap[hd] = node.val
        if node.left != nil {
            queue = append(queue, node.left)
            hd--
        }
        if node.right != nil {
            queue = append(queue, node.right)
            hd++
        }
    }
    // code to extract and return bottom view omitted
    return nil
}

medium

A. Queue is not initialized properly

B. Function returns nil instead of bottom view slice

C. Map is declared with wrong type

D. Horizontal distance (hd) is not tracked per node, causing wrong mapping

Solution

1. Step 1: Analyze horizontal distance tracking

   The variable hd is a single integer updated globally, but each node can have different hd. It should be tracked per node, e.g., by storing node and hd together in queue.

2. Step 2: Identify impact of error

   Because hd is not per node, hdMap updates will be incorrect, leading to wrong bottom view.

3. Final Answer:

   Horizontal distance (hd) is not tracked per node, causing wrong mapping -> Option D

4. Quick Check:

   Track hd per node, not globally [OK]

Hint: Track horizontal distance with each node in queue [OK]

Common Mistakes:

• Updating hd globally instead of per node
• Ignoring nil root check
• Returning nil without result

5. You want to print the bottom view of a binary tree but only for nodes with horizontal distance between -1 and 1 inclusive. How would you modify the standard bottom view algorithm to achieve this?

hard

A. Store all nodes in map, then filter keys between -1 and 1 before printing

B. Ignore nodes outside horizontal distance range during traversal

C. Use a stack instead of queue for traversal

D. Traverse tree in preorder and print nodes with hd between -1 and 1

Solution

1. Step 1: Understand the requirement

   To correctly get bottom view for hd [-1,1], must visit entire tree as in-range hd nodes may be reached via out-of-range parents.

2. Step 2: Standard traversal with filtered output

   Run standard level order, update map for all hd. When printing, iterate only over keys -1 to 1 in sorted order.

3. Final Answer:

   Store all nodes in map, then filter keys between -1 and 1 before printing -> Option A

4. Quick Check:

   Traverse all, map all hd, print filtered keys [OK]

Hint: Traverse all nodes, filter map keys when printing [OK]

Common Mistakes:

• Ignoring out-of-range nodes during traversal misses deeper in-range nodes
• Using stack breaks level order
• Preorder traversal disrupts bottom view order