Bottom View of Binary Tree in DSA Rust - Build from Scratch

Bottom View of Binary Tree

📖 Scenario: You are working on a program that helps visualize a binary tree from different angles. One useful view is the bottom view, which shows the nodes visible when looking at the tree from the bottom.Imagine a tree of buildings where you want to see which buildings are visible from the street level behind them.

🎯 Goal: Build a Rust program that constructs a binary tree, calculates the bottom view of the tree, and prints the nodes visible from the bottom in order from left to right.

📋 What You'll Learn

Create a binary tree with specific nodes and structure

Use a variable to track horizontal distances of nodes

Implement logic to find the bottom view of the binary tree

Print the bottom view nodes in left-to-right order

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree is useful in graphical applications, geographical mapping, and network routing visualization where understanding the visible nodes from a certain perspective is important.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and systems that require spatial or hierarchical data visualization.

1

Create the Binary Tree Structure

Create a struct called Node with fields data: i32, left: Option, and right: Option<Box<Node>>. Then create a binary tree with root node 20, left child 8, right child 22, left child of 8 as 5, right child of 8 as 3, left child of 3 as 10, and right child of 3 as 14.

DSA Rust

// Define the Node struct and create the binary tree as described
// Your code here

Hint

Define the Node struct with data, left, and right fields. Use Option<Box<Node>> for children. Then build the tree by assigning children to the root and its descendants.

2

Add a Map to Track Horizontal Distances

Add a mutable std::collections::BTreeMap<i32, (i32, i32)> called hd_map to store horizontal distance as key and a tuple of node data and level as value. Also add a helper function bottom_view_util that takes a reference to a Node, horizontal distance hd: i32, level lvl: i32, and mutable reference to hd_map.

DSA Rust

struct Node {
    data: i32,
    left: Option>,
    right: Option>,
}

fn new_node(data: i32) -> Box {
    Box::new(Node {
        data,
        left: None,
        right: None,
    })
}

use std::collections::BTreeMap;

// Add hd_map and bottom_view_util function below
// Your code here

Hint

Use a BTreeMap to keep keys sorted by horizontal distance. The helper function should update the map only if the current node is at a deeper or equal level than the stored one.

3

Implement Bottom View Logic

In main, create a mutable BTreeMap<i32, (i32, i32)> called hd_map. Call bottom_view_util with &Some(root), horizontal distance 0, level 0, and mutable reference to hd_map. Then create a vector bottom_view by collecting the node data from hd_map in order of horizontal distance.

DSA Rust

struct Node {
    data: i32,
    left: Option>,
    right: Option>,
}

fn new_node(data: i32) -> Box {
    Box::new(Node {
        data,
        left: None,
        right: None,
    })
}

use std::collections::BTreeMap;

fn bottom_view_util(node: &Option>, hd: i32, lvl: i32, hd_map: &mut BTreeMap) {
    if let Some(ref n) = node {
        if !hd_map.contains_key(&hd) || hd_map[&hd].1 <= lvl {
            hd_map.insert(hd, (n.data, lvl));
        }
        bottom_view_util(&n.left, hd - 1, lvl + 1, hd_map);
        bottom_view_util(&n.right, hd + 1, lvl + 1, hd_map);
    }
}

fn main() {
    let mut root = new_node(20);
    root.left = Some(new_node(8));
    root.right = Some(new_node(22));
    if let Some(ref mut left) = root.left {
        left.left = Some(new_node(5));
        left.right = Some(new_node(3));
        if let Some(ref mut right) = left.right {
            right.left = Some(new_node(10));
            right.right = Some(new_node(14));
        }
    }

    // Create hd_map and call bottom_view_util
    // Collect bottom view nodes into a vector
    // Your code here
}

Hint

Create the map, call the helper with root and initial horizontal distance and level 0. Then extract the node data from the map values into a vector for the bottom view.

4

Print the Bottom View Nodes

Print the bottom_view vector elements separated by spaces using println!. This will show the bottom view nodes from left to right.

DSA Rust

struct Node {
    data: i32,
    left: Option>,
    right: Option>,
}

fn new_node(data: i32) -> Box {
    Box::new(Node {
        data,
        left: None,
        right: None,
    })
}

use std::collections::BTreeMap;

fn bottom_view_util(node: &Option>, hd: i32, lvl: i32, hd_map: &mut BTreeMap) {
    if let Some(ref n) = node {
        if !hd_map.contains_key(&hd) || hd_map[&hd].1  = BTreeMap::new();
    bottom_view_util(&Some(root), 0, 0, &mut hd_map);
    let bottom_view: Vec = hd_map.values().map(|&(data, _)| data).collect();

    // Print bottom_view nodes separated by spaces
    // Your code here
}

Hint

Use a for loop to print each element of bottom_view followed by a space. Then print a newline.

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