Bottom View of Binary Tree in DSA Rust

Mental Model

We want to see the nodes visible if we look at the tree from the bottom. Each vertical line shows only the lowest node.

Analogy: Imagine standing under a tree and looking up. You only see the lowest leaves or branches directly above you, not the ones hidden behind.

       1
      / \
     2   3
    / \   \
   4   5   6

Vertical lines:
-2    -1    0    1    2
 4  -> 2  -> 5  -> 3  -> 6
          ↑
        root
Bottom view shows nodes: 4, 2, 5, 3, 6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Find the bottom view nodes of the tree, i.e., nodes visible from the bottom for each vertical line.

Step 1: Start BFS from root (1) at horizontal distance (hd) 0

Queue: [(1, hd=0)]
Bottom map: {}

Why: We begin from root to explore all nodes level by level with their horizontal distances

Step 2: Pop (1,0), update bottom map hd=0 with node 1

Queue: []
Bottom map: {0:1}
Add left child (2, hd=-1), right child (3, hd=1)

Why: Node 1 is the first at hd=0, so it is currently the bottom node there

Step 3: Pop (2,-1), update bottom map hd=-1 with node 2

Queue: [(3,1)]
Bottom map: {-1:2, 0:1}
Add left child (4, hd=-2), right child (5, hd=0)

Why: Node 2 is the lowest so far at hd=-1

Step 4: Pop (3,1), update bottom map hd=1 with node 3

Queue: [(4,-2), (5,0)]
Bottom map: {-1:2, 0:1, 1:3}
Add right child (6, hd=2)

Why: Node 3 is the lowest so far at hd=1

Step 5: Pop (4,-2), update bottom map hd=-2 with node 4

Queue: [(5,0), (6,2)]
Bottom map: {-2:4, -1:2, 0:1, 1:3}

Why: Node 4 is the lowest so far at hd=-2

Step 6: Pop (5,0), update bottom map hd=0 with node 5 (overwrites 1)

Queue: [(6,2)]
Bottom map: {-2:4, -1:2, 0:5, 1:3}

Why: Node 5 is lower than 1 at hd=0, so it replaces it

Step 7: Pop (6,2), update bottom map hd=2 with node 6

Queue: []
Bottom map: {-2:4, -1:2, 0:5, 1:3, 2:6}

Why: Node 6 is the lowest so far at hd=2

Result:

Bottom view nodes in order of hd: 4 -> 2 -> 5 -> 3 -> 6

Annotated Code

DSA Rust

use std::collections::{HashMap, VecDeque};

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn bottom_view(root: Option<Box<TreeNode>>) -> Vec<i32> {
    if root.is_none() {
        return vec![];
    }

    let mut queue: VecDeque<(Box<TreeNode>, i32)> = VecDeque::new();
    let mut bottom_map: HashMap<i32, i32> = HashMap::new();

    queue.push_back((root.unwrap(), 0));

    while let Some((node, hd)) = queue.pop_front() {
        // Update bottom_map with current node for hd
        bottom_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<i32> = bottom_map.keys().cloned().collect();
    keys.sort();

    keys.iter().map(|k| *bottom_map[k]).collect()
}

fn main() {
    // Build tree:
    //        1
    //       / \
    //      2   3
    //     / \   \
    //    4   5   6

    let mut root = Box::new(TreeNode::new(1));
    let mut node2 = Box::new(TreeNode::new(2));
    let mut node3 = Box::new(TreeNode::new(3));
    let node4 = Box::new(TreeNode::new(4));
    let node5 = Box::new(TreeNode::new(5));
    let node6 = Box::new(TreeNode::new(6));

    node2.left = Some(node4);
    node2.right = Some(node5);
    node3.right = Some(node6);

    root.left = Some(node2);
    root.right = Some(node3);

    let result = bottom_view(Some(root));
    for val in result {
        print!("{} ", val);
    }
    println!();
}

queue.push_back((root.unwrap(), 0));

Start BFS from root with horizontal distance 0

bottom_map.insert(hd, node.val);

Update bottom map with current node at horizontal distance hd

if let Some(left) = node.left { queue.push_back((left, hd - 1)); }

Add left child with hd-1 to queue for BFS

if let Some(right) = node.right { queue.push_back((right, hd + 1)); }

Add right child with hd+1 to queue for BFS

keys.sort();

Sort horizontal distances to output bottom view left to right

keys.iter().map(|k| *bottom_map[k]).collect()

Collect bottom view nodes in order of horizontal distance

Output

4 2 5 3 6 

Complexity Analysis

Time: O(n) because we visit each node once in BFS

Space: O(n) for queue and hashmap storing nodes and horizontal distances

vs Alternative: Compared to recursive vertical order traversal, BFS with hashmap is simpler and efficient for bottom view

Edge Cases

Empty tree

Returns empty list as no nodes exist

DSA Rust

if root.is_none() { return vec![]; }

Single node tree

Returns list with only root node value

DSA Rust

bottom_map.insert(hd, node.val);

Tree with multiple nodes at same horizontal distance and level

Bottom-most node overwrites previous nodes at same hd

DSA Rust

bottom_map.insert(hd, node.val);

When to Use This Pattern

When asked to find nodes visible from bottom or side in a tree, use BFS with horizontal distances and a map to track last nodes at each vertical line.

Common Mistakes

Mistake: Using DFS instead of BFS causing incorrect bottom nodes because deeper nodes might be missed
Fix: Use BFS to process nodes level by level ensuring bottom-most nodes overwrite top ones

Mistake: Not updating the map for nodes at same horizontal distance, so top nodes remain instead of bottom
Fix: Always overwrite the map entry for a horizontal distance when a new node is found

Summary

Finds the nodes visible when looking at a binary tree from the bottom.

Use when you need to see the lowest nodes at each vertical line of the tree.

Track horizontal distances with BFS and overwrite nodes to keep the bottom-most visible.

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