Vertical Order Traversal of Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Vertical Order Traversal for a Simple Tree

What is the output of the vertical order traversal for the following binary tree?

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

DSA Rust

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

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

fn vertical_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    if root.is_none() {
        return vec![];
    }
    let mut column_table: BTreeMap<i32, Vec<i32>> = BTreeMap::new();
    let mut queue: VecDeque<(Box<TreeNode>, i32)> = VecDeque::new();
    queue.push_back((root.unwrap(), 0));

    while let Some((node, col)) = queue.pop_front() {
        column_table.entry(col).or_default().push(node.val);
        if let Some(left) = node.left {
            queue.push_back((left, col - 1));
        }
        if let Some(right) = node.right {
            queue.push_back((right, col + 1));
        }
    }

    column_table.into_values().collect()
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
    }));

    let result = vertical_order(root);
    println!("{:?}", result);
}

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

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

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

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

💡 Hint

Think about columns from left to right and nodes in each column from top to bottom.

The vertical order traversal groups nodes by their horizontal distance from the root. Here, 4 is at column -2, 2 at -1, 1 at 0, 3 at 1, and 5 at 2. So the output is [[4], [2], [1], [3], [5]].

❓ Predict Output

intermediate

Vertical Order Traversal Output with Multiple Nodes in Same Column

What is the output of the vertical order traversal for this binary tree?

Tree structure:
3
/ \
9 8
/ \ / \
4 0 1 7

DSA Rust

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

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

fn vertical_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    if root.is_none() {
        return vec![];
    }
    let mut column_table: BTreeMap<i32, Vec<i32>> = BTreeMap::new();
    let mut queue: VecDeque<(Box<TreeNode>, i32)> = VecDeque::new();
    queue.push_back((root.unwrap(), 0));

    while let Some((node, col)) = queue.pop_front() {
        column_table.entry(col).or_default().push(node.val);
        if let Some(left) = node.left {
            queue.push_back((left, col - 1));
        }
        if let Some(right) = node.right {
            queue.push_back((right, col + 1));
        }
    }

    column_table.into_values().collect()
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 3,
        left: Some(Box::new(TreeNode {
            val: 9,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 0, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 8,
            left: Some(Box::new(TreeNode { val: 1, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 7, left: None, right: None })),
        })),
    }));

    let result = vertical_order(root);
    println!("{:?}", result);
}

A [[4], [9, 0], [3, 1], [8, 7]]

B [[4, 9], [3, 0, 1], [8, 7]]

C [[4], [9], [3, 0, 1], [8], [7]]

D [[9, 4], [3, 0, 1], [8, 7]]

💡 Hint

Remember nodes are grouped by column, and within each column, nodes appear top to bottom.

Nodes 4 at column -2, 9 at -1, 3, 0, 1 at 0, 8 at 1, and 7 at 2. The order inside column 0 is top to bottom: 3, then 0, then 1.

🔧 Debug

advanced

Identify the Error in Vertical Order Traversal Implementation

The following Rust code attempts vertical order traversal but produces incorrect output. What is the main reason?

Code snippet:

while let Some((node, col)) = queue.pop_front() {
    column_table.entry(col).or_default().push(node.val);
    if node.left.is_some() {
        queue.push_back((node.left.unwrap(), col - 1));
    }
    if node.right.is_some() {
        queue.push_back((node.right.unwrap(), col + 1));
    }
}

A Using unwrap() on Option without checking causes panic if None is encountered.

B The code does not use a BTreeMap, so columns are unordered.

C The queue is not initialized before the loop, so it is empty.

D The code uses depth-first traversal instead of breadth-first traversal.

💡 Hint

Consider what happens if left or right child is None.

Calling unwrap() on an Option that is None causes a runtime panic. The code checks is_some() but unwrap() is called twice separately, which can cause panic if the Option changes between calls or if unwrap is called without is_some check.

❓ Predict Output

advanced

Output of Vertical Order Traversal with Negative and Positive Columns

Given this binary tree, what is the vertical order traversal output?

Tree structure:
10
/ \
5 15
/ \ \
3 7 18

DSA Rust

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

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

fn vertical_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    if root.is_none() {
        return vec![];
    }
    let mut column_table: BTreeMap<i32, Vec<i32>> = BTreeMap::new();
    let mut queue: VecDeque<(Box<TreeNode>, i32)> = VecDeque::new();
    queue.push_back((root.unwrap(), 0));

    while let Some((node, col)) = queue.pop_front() {
        column_table.entry(col).or_default().push(node.val);
        if let Some(left) = node.left {
            queue.push_back((left, col - 1));
        }
        if let Some(right) = node.right {
            queue.push_back((right, col + 1));
        }
    }

    column_table.into_values().collect()
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 10,
        left: Some(Box::new(TreeNode {
            val: 5,
            left: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 7, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 15,
            left: None,
            right: Some(Box::new(TreeNode { val: 18, left: None, right: None })),
        })),
    }));

    let result = vertical_order(root);
    println!("{:?}", result);
}

A [[5, 3], [10, 7], [15, 18]]

B [[3], [5, 7], [10], [15, 18]]

C [[3, 5], [7, 10], [15, 18]]

D [[3], [5], [10, 7], [15], [18]]

💡 Hint

Remember columns are horizontal distances from root: left is negative, right is positive.

Nodes 3 at column -2, 5 at -1, 10 and 7 at 0, 15 at 1, and 18 at 2. The order inside column 0 is top to bottom: 10 then 7.

🧠 Conceptual

expert

Understanding Data Structures Used in Vertical Order Traversal

Which data structure is best suited to store nodes grouped by their vertical columns in vertical order traversal, ensuring columns are processed from left to right?

Options:

A LinkedList storing nodes in insertion order

B BTreeMap with keys as column indices (ordered)

C Vector indexed by column indices (may waste space for negative indices)

D HashMap with keys as column indices (unordered)

💡 Hint

Think about the need to keep columns sorted by their horizontal distance.

BTreeMap keeps keys sorted, which allows easy retrieval of columns from left to right. HashMap is unordered, Vector can't handle negative indices easily, and LinkedList does not provide key-based access.

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