Vertical Order Traversal of Binary Tree in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the TreeNode struct with optional left and right children.

DSA Rust

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

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

Drag options to blanks, or click blank then click option'

ASome(Box::new(TreeNode::new(val)))

BSome(Box::new(val))

CNone

DSome(TreeNode::new(val))

Attempts:

3 left

💡 Hint

Common Mistakes

Using Some without Box causes type mismatch.

Trying to initialize children with values instead of None.

When creating a new TreeNode, the left and right children are initially empty, so we use None.

2fill in blank

medium

Complete the code to insert a node into the vertical order map with its horizontal distance.

DSA Rust

use std::collections::BTreeMap;
use std::collections::VecDeque;

fn vertical_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut map: BTreeMap<i32, Vec<i32>> = BTreeMap::new();
    let mut queue: VecDeque<(Box<TreeNode>, i32)> = VecDeque::new();

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

    while let Some((node, hd)) = queue.pop_front() {
        map.entry(hd).or_insert(Vec::new()).[1](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));
        }
    }

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

Drag options to blanks, or click blank then click option'

Apush

Binsert

Cpush_back

Dappend

Attempts:

3 left

💡 Hint

Common Mistakes

Using push_back on Vec causes error because Vec does not have push_back.

Using insert overwrites existing values.

Vec in Rust uses push to add elements at the end.

3fill in blank

hard

Fix the error in the BFS loop to correctly handle Option when pushing children.

DSA Rust

while let Some((node, hd)) = queue.pop_front() {
    map.entry(hd).or_insert(Vec::new()).push(node.val);

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

Drag options to blanks, or click blank then click option'

A.as_ref()

B.take()

C.unwrap()

D.clone()

Attempts:

3 left

💡 Hint

Common Mistakes

Using unwrap moves the node and causes borrow errors.

Using as_ref returns a reference, but queue expects owned Box.

We clone the Box to push it into the queue without moving the original.

4fill in blank

hard

Fill both blanks to correctly initialize the queue and map for vertical order traversal.

DSA Rust

use std::collections::[1];

fn vertical_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut map: [2]<i32, Vec<i32>> = [1]::new();
    let mut queue: VecDeque<(Box<TreeNode>, i32)> = VecDeque::new();

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

    // BFS loop ...
}

Drag options to blanks, or click blank then click option'

ABTreeMap

BHashMap

CVecDeque

DLinkedList

Attempts:

3 left

💡 Hint

Common Mistakes

Using HashMap causes unordered output.

Using LinkedList is not suitable for map.

We use BTreeMap to keep keys sorted and initialize it with BTreeMap::new().

5fill in blank

hard

Fill all three blanks to complete the BFS loop that processes nodes and updates the map and queue.

DSA Rust

while let Some((node, hd)) = queue.pop_front() {
    map.entry(hd).or_insert(Vec::new()).[1](node.val);

    if let Some(left) = node.left [2] {
        queue.push_back((left.[3](), hd - 1));
    }
    if let Some(right) = node.right {
        queue.push_back((right.clone(), hd + 1));
    }
}

Drag options to blanks, or click blank then click option'

Apush

Bclone

Dtake

Attempts:

3 left

💡 Hint

Common Mistakes

Using take moves the node and causes errors.

Forgetting to clone causes ownership errors.

We push node.val into the vector, clone left child to push into queue, and call clone() on left.

Practice

1. What does vertical order traversal of a binary tree mean?

easy

A. Nodes are grouped by their vertical columns from left to right

B. Nodes are visited level by level from top to bottom

C. Nodes are visited in preorder (root, left, right)

D. Nodes are visited in inorder (left, root, right)

Solution

1. Step 1: Understand vertical order traversal

   Vertical order traversal groups nodes by their vertical position (column) relative to the root.

2. Step 2: Compare with other traversals

   Unlike level order or inorder, vertical order focuses on columns from left to right.

3. Final Answer:

   Nodes are grouped by their vertical columns from left to right -> Option A

4. Quick Check:

   Vertical order = group by vertical columns [OK]

Hint: Think columns, not levels or order [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking vertical order is preorder or inorder
• Ignoring horizontal distance from root

2. Which Rust data structure is best to store nodes grouped by their vertical column during vertical order traversal?

easy

A. Vec<i32>

B. HashMap

C. BinaryHeap<i32>

D. LinkedList<i32>

Solution

1. Step 1: Identify grouping need

   We need to group nodes by their vertical column index (an integer key).

2. Step 2: Choose suitable Rust structure

   HashMap maps column indices to lists of node values, perfect for grouping.

3. Final Answer:

   HashMap -> Option B

4. Quick Check:

   Use HashMap for key-value grouping [OK]

Hint: Use HashMap for key-based grouping [OK]

Common Mistakes:

• Using Vec alone without keys
• Using BinaryHeap which is for priority queues
• Using LinkedList which is inefficient here

3. Given the binary tree:

    1
   / \
  2   3
 /     \
4       5

What is the vertical order traversal output?

medium

A. [[4], [2], [1], [3], [5]]

B. [[1], [2, 3], [4, 5]]

C. [[4, 2], [1, 3], [5]]

D. [[5], [3], [1], [2], [4]]

Solution

1. Step 1: Assign vertical columns

   Root 1 is column 0; left child 2 is -1; left child of 2 (4) is -2; right child 3 is +1; right child of 3 (5) is +2.

2. Step 2: Group nodes by columns

   Column -2: [4], -1: [2], 0: [1], 1: [3], 2: [5].

3. Final Answer:

   [[4], [2], [1], [3], [5]] -> Option A

4. Quick Check:

   Group nodes by horizontal distance [OK]

Hint: Track horizontal distance from root [OK]

Common Mistakes:

• Mixing vertical order with level order
• Grouping nodes incorrectly by level
• Ignoring negative column indices

4. Consider this Rust code snippet for vertical order traversal:

fn vertical_order(root: Option) -> Vec {
    let mut map = std::collections::HashMap::new();
    fn dfs(node: &Option, col: i32, map: &mut HashMap) {
        if let Some(n) = node {
            map.entry(col).or_insert(vec![]).push(n.val);
            dfs(&n.left, col - 1, map);
            dfs(&n.right, col + 1, map);
        }
    }
    dfs(&root, 0, &mut map);
    map.values().cloned().collect()
}

What is the main bug causing incorrect output?

medium

A. DFS should use BFS for vertical order

B. map.entry() should use get_mut() instead

C. col variable should start at 1, not 0

D. map.values() does not guarantee sorted column order

Solution

1. Step 1: Analyze map usage

   HashMap stores columns but values() returns in arbitrary order, not sorted by column.

2. Step 2: Understand output order requirement

   Vertical order requires columns sorted from left to right, so keys must be sorted before collecting values.

3. Final Answer:

   map.values() does not guarantee sorted column order -> Option D

4. Quick Check:

   Sort keys before output [OK]

Hint: Sort keys before collecting values [OK]

Common Mistakes:

• Assuming HashMap preserves order
• Thinking BFS is mandatory for vertical order
• Starting column index incorrectly

5. You want to modify vertical order traversal to also sort nodes by their depth (top to bottom) within the same vertical column. Which approach is best?

hard

A. Traverse tree in preorder and collect nodes without sorting

B. Use a Vec indexed by column and append nodes as visited

C. Use a HashMap> and sort each vector by depth before output

D. Use a BinaryHeap keyed by node value only

Solution

1. Step 1: Understand sorting by depth need

   Nodes in same vertical column must be ordered by their depth (distance from root).

2. Step 2: Choose data structure to store depth info

   Store (depth, value) pairs in HashMap for each column, then sort by depth before output.

3. Final Answer:

   Use a HashMap> and sort each vector by depth before output -> Option C

4. Quick Check:

   Store depth info and sort before output [OK]

Hint: Keep depth info to sort nodes in columns [OK]

Common Mistakes:

• Ignoring depth and outputting unsorted nodes
• Using BinaryHeap without depth key
• Appending nodes without sorting