Bottom View of Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom View for a Simple Binary Tree

What is the bottom view of the following binary tree after running the given Rust code?

DSA Rust

use std::collections::BTreeMap;

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

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

fn bottom_view(root: &Option<Box<Node>>) -> Vec<i32> {
    use std::collections::VecDeque;
    let mut map = BTreeMap::new();
    let mut queue = VecDeque::new();

    if let Some(node) = root {
        queue.push_back((node, 0));
    }

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

    map.values().cloned().collect()
}

fn main() {
    let mut root = Box::new(Node::new(20));
    root.left = Some(Box::new(Node::new(8)));
    root.right = Some(Box::new(Node::new(22)));
    root.left.as_mut().unwrap().left = Some(Box::new(Node::new(5)));
    root.left.as_mut().unwrap().right = Some(Box::new(Node::new(3)));
    root.right.as_mut().unwrap().right = Some(Box::new(Node::new(25)));
    root.left.as_mut().unwrap().right.as_mut().unwrap().left = Some(Box::new(Node::new(10)));
    root.left.as_mut().unwrap().right.as_mut().unwrap().right = Some(Box::new(Node::new(14)));

    let result = bottom_view(&Some(root));
    println!("{:?}", result);
}

A [5, 10, 3, 22, 25]

B [5, 8, 3, 14, 25]

C [8, 10, 3, 14, 22]

D [5, 10, 3, 14, 25]

💡 Hint

Remember bottom view shows the last node at each horizontal distance from left to right.

The bottom view is calculated by tracking the horizontal distance (hd) of each node from the root. The last node encountered at each hd during level order traversal is stored. For this tree, the bottom nodes at hd -2 to 2 are 5, 10, 3, 14, and 25 respectively.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Bottom View

In the bottom view of a binary tree, what does the 'horizontal distance' (hd) represent?

A The depth of the node from the root

B The distance of the node from the root measured horizontally, with root at 0, left child hd-1, right child hd+1

C The vertical level of the node in the tree

D The number of nodes in the subtree rooted at that node

💡 Hint

Think about how nodes are positioned left or right relative to the root.

Horizontal distance is a measure of how far left or right a node is from the root. The root has hd 0, left child decreases hd by 1, right child increases hd by 1. This helps identify nodes vertically aligned.

🔧 Debug

advanced

Identify the Bug in Bottom View Implementation

What error will the following Rust code produce when computing bottom view of a binary tree?

DSA Rust

fn bottom_view(root: &Option<Box<Node>>) -> Vec<i32> {
    use std::collections::HashMap;
    use std::collections::VecDeque;
    let mut map = HashMap::new();
    let mut queue = VecDeque::new();

    if let Some(node) = root {
        queue.push_back((node, 0));
    }

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

    let mut result = Vec::new();
    for key in map.keys() {
        result.push(map[key]);
    }
    result
}

A Empty vector returned because queue is never filled

B Compilation error due to missing semicolon

C The output vector is unordered, so bottom view nodes are not sorted by horizontal distance

D Runtime panic due to borrowing error

💡 Hint

Check how the map keys are iterated and collected.

The code uses a HashMap which does not maintain order of keys. Iterating over keys and pushing values results in an unordered bottom view. The bottom view requires nodes sorted by horizontal distance, so a BTreeMap should be used instead.

🚀 Application

advanced

Bottom View with Overlapping Nodes at Same Horizontal Distance

Given a binary tree where multiple nodes share the same horizontal distance and depth, which node appears in the bottom view?

A The node with the largest depth (lowest level) at that horizontal distance

B The node with the smallest value

C The node that appears last in level order traversal at that horizontal distance

D The node that appears first in preorder traversal at that horizontal distance

💡 Hint

Bottom view shows the lowest visible node at each horizontal distance.

The bottom view shows the node visible when looking from the bottom. If multiple nodes share the same horizontal distance, the one with the greatest depth (lowest level) is visible.

❓ Predict Output

expert

Output of Bottom View for Complex Binary Tree with Negative and Positive Values

What is the output of the bottom view function for the following binary tree?

DSA Rust

use std::collections::BTreeMap;

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

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

fn bottom_view(root: &Option<Box<Node>>) -> Vec<i32> {
    use std::collections::VecDeque;
    let mut map = BTreeMap::new();
    let mut queue = VecDeque::new();

    if let Some(node) = root {
        queue.push_back((node, 0));
    }

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

    map.values().cloned().collect()
}

fn main() {
    let mut root = Box::new(Node::new(1));
    root.left = Some(Box::new(Node::new(2)));
    root.right = Some(Box::new(Node::new(3)));
    root.left.as_mut().unwrap().left = Some(Box::new(Node::new(4)));
    root.left.as_mut().unwrap().right = Some(Box::new(Node::new(5)));
    root.right.as_mut().unwrap().left = Some(Box::new(Node::new(6)));
    root.right.as_mut().unwrap().right = Some(Box::new(Node::new(7)));
    root.left.as_mut().unwrap().right.as_mut().unwrap().right = Some(Box::new(Node::new(8)));
    root.right.as_mut().unwrap().left.as_mut().unwrap().left = Some(Box::new(Node::new(9)));

    let result = bottom_view(&Some(root));
    println!("{:?}", result);
}

A [4, 2, 9, 6, 8, 7]

B [4, 2, 9, 5, 8, 7]

C [4, 2, 9, 6, 3, 7]

D [4, 2, 5, 6, 8, 7]

💡 Hint

Track horizontal distances and update with the last node at each during level order traversal.

The bottom view nodes from left to right correspond to horizontal distances -2 to 3. The nodes at these distances are 4, 2, 9, 6, 8, and 7 respectively after level order traversal updates.

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