Vertical Order Traversal of Binary Tree in DSA Rust - Build from Scratch

Vertical Order Traversal of Binary Tree

📖 Scenario: Imagine you are working with a family tree app that shows family members vertically aligned by their generation and horizontally by their family branches. You want to display the family members in vertical order from left to right.

🎯 Goal: Build a Rust program that performs vertical order traversal on a binary tree. The program will group nodes by their vertical columns and print the nodes in each vertical column from top to bottom.

📋 What You'll Learn

Create a binary tree using a TreeNode struct with val, left, and right fields

Create a root node with the exact structure given

Create a HashMap to store nodes by their vertical column index

Use a VecDeque as a queue to perform level order traversal with column tracking

Implement vertical order traversal logic using a queue and hashmap

Print the vertical order traversal result as a vector of vectors of integers

💡 Why This Matters

🌍 Real World

Vertical order traversal helps in displaying hierarchical data visually aligned by columns, such as family trees, organizational charts, or layered maps.

💼 Career

Understanding tree traversals and data grouping is essential for software engineers working on UI rendering, data visualization, and complex data structure manipulation.

1

Create the binary tree structure and root node

Define a TreeNode struct with val: i32, left: Option>, and right: Option>. Then create a variable root representing this exact tree:

1
/ \ 2 3
/ \ \ 4 5 6

Use Some(Box::new(TreeNode { ... })) to create nodes exactly as shown.

DSA Rust

# Define TreeNode struct and create root node
# Your code here

Hint

Use Option> for left and right children. Create nodes bottom-up using Some(Box::new(TreeNode { ... })).

2

Set up a HashMap and a queue for traversal

Add these two variables inside main() after root:
1. A mutable HashMap> called columns to store nodes by their vertical column index.
2. A VecDeque called queue to hold tuples of (Option>, i32) representing nodes and their column indices.
Initialize queue by pushing (root, 0).

DSA Rust

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

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: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
        })),
    }));

    // Create a HashMap called columns
    // Create a VecDeque called queue and push (root, 0)
    // Your code here
}

Hint

Import HashMap and VecDeque from std::collections. Initialize columns as empty and queue with (root, 0).

3

Implement vertical order traversal logic

Write a while loop that runs while queue is not empty. Inside the loop:
1. Pop the front element from queue into (node_option, col).
2. If node_option is Some(node), push node.val into columns at key col.
3. Push the left child with column col - 1 and right child with column col + 1 into queue if they exist.
Use columns.entry(col).or_insert(Vec::new()).push(node.val) to insert values.

DSA Rust

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

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

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: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
        })),
    }));

    let mut columns: HashMap> = HashMap::new();
    let mut queue: VecDeque>, i32)> = VecDeque::new();
    queue.push_back((root, 0));

    // Your code here
}

Hint

Use while let Some((node_option, col)) = queue.pop_front() to loop. Use if let Some(node) = node_option to access node. Insert node.val into columns at col. Push left child with col - 1 and right child with col + 1 into queue.

4

Print the vertical order traversal result

Create a mutable vector sorted_cols containing all keys from columns. Sort sorted_cols in ascending order. Then create a vector result by collecting the values from columns in the order of sorted_cols. Finally, print result using println!("{:?}", result).

DSA Rust

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

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

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: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
        })),
    }));

    let mut columns: HashMap> = HashMap::new();
    let mut queue: VecDeque>, i32)> = VecDeque::new();
    queue.push_back((root, 0));

    while let Some((node_option, col)) = queue.pop_front() {
        if let Some(node) = node_option {
            columns.entry(col).or_insert(Vec::new()).push(node.val);
            queue.push_back((node.left, col - 1));
            queue.push_back((node.right, col + 1));
        }
    }

    // Your code here
}

Hint

Sort the keys of columns and collect their values in order. Print the final vector of vectors.

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