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

↓

Enqueue right child with hd+1

↓

After traversal, extract nodes with max depth per horizontal distance

↓

Print bottom view from min hd to max hd

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

Execution Sample

DSA Rust

struct Node {
  val: i32,
  left: Option<Box<Node>>,
  right: Option<Box<Node>>,
}

// Bottom view function uses queue and map for hd tracking

This code traverses the binary tree level-wise, tracks horizontal distances, and records the bottom-most node at each horizontal distance.

Execution Table

Step	Operation	Node Visited (val)	Horizontal Distance (hd)	Queue State (val, hd)	Bottom View Map (hd: val)	Visual State
1	Start at root	20	0	[(20,0)]	{0:20}	20(0)
2	Dequeue node	20	0	[]	{0:20}	20(0)
3	Enqueue left child	8	-1	[(8,-1)]	{0:20}	8(-1) <- 20(0)
4	Enqueue right child	22	1	[(8,-1),(22,1)]	{0:20}	8(-1) <- 20(0) -> 22(1)
5	Dequeue node	8	-1	[(22,1)]	{-1:8,0:20}	8(-1) <- 20(0) -> 22(1)
6	Enqueue left child	5	-2	[(22,1),(5,-2)]	{-1:8,0:20}	5(-2) <- 8(-1) <- 20(0) -> 22(1)
7	Enqueue right child	3	0	[(22,1),(5,-2),(3,0)]	{-1:8,0:20}	5(-2) <- 8(-1) <- 20(0) -> 22(1)
8	Dequeue node	22	1	[(5,-2),(3,0)]	{-1:8,0:20,1:22}	5(-2) <- 8(-1) <- 20(0) -> 22(1)
9	Enqueue right child	25	2	[(5,-2),(3,0),(25,2)]	{-1:8,0:20,1:22}	5(-2) <- 8(-1) <- 20(0) -> 22(1) -> 25(2)
10	Dequeue node	5	-2	[(3,0),(25,2)]	{-2:5,-1:8,0:20,1:22}	5(-2) <- 8(-1) <- 20(0) -> 22(1) -> 25(2)
11	Dequeue node	3	0	[(25,2)]	{-2:5,-1:8,0:3,1:22}	5(-2) <- 8(-1) <- 3(0) -> 22(1) -> 25(2)
12	Dequeue node	25	2	[]	{-2:5,-1:8,0:3,1:22,2:25}	5(-2) <- 8(-1) <- 3(0) -> 22(1) -> 25(2)
13	Traversal complete	-	-	[]	{-2:5,-1:8,0:3,1:22,2:25}	Bottom view nodes collected

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

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 11	Final
Queue	[(20,0)]	[]	[(22,1),(5,-2),(3,0)]	[(25,2)]	[]
Bottom View Map	{}	{0:20}	{-1:8,0:20}	{-2:5,-1:8,0:3,1:22}	{-2:5,-1:8,0:3,1:22,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 and is lower in the tree, so it replaces 20 in the bottom view map (see steps 7 and 11 in execution_table).

Why do we use horizontal distance (hd) and not just node values to determine bottom view?

Horizontal distance helps group nodes vertically aligned. Bottom view shows the lowest node at each hd, not just any node value (see concept_flow and execution_table hd column).

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

Queue enables level order traversal, ensuring nodes are visited top to bottom and left to right, so bottom nodes overwrite top ones correctly (see concept_flow and execution_table queue state).

Visual Quiz - 3 Questions

Look at the execution_table at step 11, what is the bottom view map entry for horizontal distance 0?

A 20

B 3

C 8

D 22

💡 Hint

Check the Bottom View Map column at step 11 in execution_table

At which step does the horizontal distance -2 first appear in the bottom view map?

A Step 6

B Step 9

C Step 10

D Step 12

💡 Hint

Look for when hd -2 is added to Bottom View Map in execution_table

If the node with value 3 was missing, how would the bottom view map at hd 0 change at the end?

A It would remain 20

B It would be 8

C It would be 22

D It would be 5

💡 Hint

Refer to variable_tracker and execution_table steps 7 and 11 for hd 0 updates

Concept Snapshot

Bottom View of Binary Tree:
- Traverse tree level-wise using a queue
- Track horizontal distance (hd) for each node
- Update map with node at hd to keep bottom-most node
- After traversal, print nodes from min to max hd
- Shows nodes visible when viewed from bottom

Full Transcript

Bottom view of a binary tree is found by traversing the tree level by level, tracking each node's horizontal distance from the root. We use a queue to visit nodes in order and a map to store the bottom-most node at each horizontal distance. When a node is visited, it updates the map for its horizontal distance, replacing any previous node at that distance because it is lower in the tree. After visiting all nodes, the map contains the bottom view nodes, which we print from the smallest to largest horizontal distance. This method ensures we see the nodes visible from the bottom of the tree.

Practice

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

easy

A. Nodes visible when the tree is viewed from the left 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 right 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 is left or right side view
• Assuming all nodes are visible in bottom view

2. Which Rust data structure is best suited to store nodes by their horizontal distance when computing bottom view?

easy

A. Vec<Node>

B. HashMap

C. LinkedList<Node>

D. BinaryHeap<Node>

Solution

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

   We need to map horizontal distances (integers) to nodes, so a key-value structure is required.

2. Step 2: Choose appropriate Rust data structure

   HashMap allows storing nodes with horizontal distance keys efficiently.

3. Final Answer:

   HashMap<i32, Node> -> Option B

4. Quick Check:

   Use HashMap for horizontal distance mapping [OK]

Hint: Use HashMap to map horizontal distance to nodes [OK]

Common Mistakes:

• Using Vec which doesn't map keys to values
• Using LinkedList which is sequential, not key-based
• Using BinaryHeap which is for priority, not mapping

3. Given the following Rust code snippet for bottom view, what is the printed output?

struct Node {
    val: i32,
    left: Option,
    right: Option,
}

// Tree:
//       1
//      / \
//     2   3
//      \   \
//       4   5

// Bottom view expected: 2 -> 4 -> 3 -> 5

fn main() {
    // Assume bottom_view function returns Vec<i32> of bottom view nodes
    let bottom = vec![2, 4, 3, 5];
    for val in bottom {
        print!("{} -> ", val);
    }
    print!("null\n");
}

medium

A. 2 -> 3 -> 4 -> 5 -> null

B. 1 -> 2 -> 3 -> 4 -> 5 -> null

C. 4 -> 2 -> 5 -> 3 -> null

D. 2 -> 4 -> 3 -> 5 -> null

Solution

1. Step 1: Understand the tree structure and bottom view

   The tree has nodes 2,4,3,5 visible from bottom at horizontal distances -1,0,1,2 respectively.

2. Step 2: Trace the printed output from the vector

   The vector contains [2,4,3,5], printed with arrows and ending with null.

3. Final Answer:

   2 -> 4 -> 3 -> 5 -> null -> Option D

4. Quick Check:

   Bottom view print matches vector [OK]

Hint: Match printed output with bottom view vector [OK]

Common Mistakes:

• Confusing node order in bottom view
• Printing all nodes instead of bottom view nodes
• Missing the final 'null' in output

4. Identify the bug in this Rust snippet for bottom view calculation:

fn bottom_view(root: Option) -> Vec<i32> {
    let mut map = std::collections::HashMap::new();
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((root.unwrap(), 0));

    while let Some((node, hd)) = queue.pop_front() {
        map.insert(hd, node.val);
        if let Some(left) = node.left {
            queue.push_back((left, hd - 1));
        }
        if let Some(right) = node.right {
            queue.push_back((right, hd + 1));
        }
    }

    let mut keys: Vec<_> = map.keys().cloned().collect();
    keys.sort();
    keys.iter().map(|k| map[k]).collect()
}

medium

A. Using unwrap() on root without checking if it's None

B. Not updating map with bottom-most node at each horizontal distance

C. Incorrect horizontal distance calculation for left child

D. Not sorting keys before collecting bottom view nodes

Solution

1. Step 1: Check root unwrap usage

   Calling unwrap() on root without checking if root is None can cause panic if tree is empty.

2. Step 2: Verify other logic correctness

   Horizontal distances and map updates are correct; keys are sorted before collecting nodes.

3. Final Answer:

   Using unwrap() on root without checking if it's None -> Option A

4. Quick Check:

   unwrap() on None causes panic [OK]

Hint: Check unwrap() usage on Option before unwrapping [OK]

Common Mistakes:

• Ignoring possibility of empty tree causing panic
• Assuming map updates only once per horizontal distance
• Forgetting to sort keys before output

5. You have a binary tree where multiple nodes share the same horizontal distance and depth. How should you modify the bottom view algorithm in Rust to ensure the node with the greatest depth is shown in the bottom view?

hard

A. Store (node value, depth) in the map and update only if new depth >= stored depth

B. Store only node values and overwrite map entry whenever a node is visited

C. Use a stack instead of queue to traverse nodes

D. Sort nodes by value before inserting into the map

Solution

1. Step 1: Understand the need to track depth

   Bottom view requires the lowest node at each horizontal distance, so depth must be tracked.

2. Step 2: Modify map to store node value and depth

   Store tuple (value, depth) and update map only if new node's depth is greater or equal to existing depth.

3. Step 3: Ignore other options

   Overwriting blindly loses depth info; stack changes traversal order; sorting by value doesn't solve depth issue.

4. Final Answer:

   Store (node value, depth) in the map and update only if new depth >= stored depth -> Option A

5. Quick Check:

   Track depth to keep bottom-most node [OK]

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

Common Mistakes:

• Ignoring node depth leading to wrong bottom view
• Overwriting map entries without depth check
• Changing traversal method without addressing depth