Vertical Order Traversal of Binary Tree in DSA Rust

Mental Model

We group tree nodes by their vertical columns and list nodes top to bottom in each column.

Analogy: Imagine standing in front of a tree and looking straight at it. Nodes that line up vertically form a column. We read nodes column by column from left to right, and within each column from top to bottom.

      1
     / \
    2   3
   / \   \
  4   5   6

Columns:  -2  -1   0    1
Nodes:   4   2 1 5  3   6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Print nodes grouped by vertical columns from left to right, top to bottom within each column.

Step 1: Start at root node 1 with column 0

Column 0: [1]
Columns so far: {0: [1]}

Why: Root is the center column, starting point for vertical indexing

Step 2: Move to left child 2 with column -1

Column -1: [2]
Column 0: [1]
Columns so far: {-1: [2], 0: [1]}

Why: Left child is one column to the left

Step 3: Move to left child 4 with column -2

Column -2: [4]
Column -1: [2]
Column 0: [1]
Columns so far: {-2: [4], -1: [2], 0: [1]}

Why: Left child again moves one column left

Step 4: Back to node 2, move to right child 5 with column 0

Column 0: [1, 5]
Column -2: [4]
Column -1: [2]
Columns so far: {-2: [4], -1: [2], 0: [1, 5]}

Why: Right child moves one column right from parent

Step 5: Back to root 1, move to right child 3 with column 1

Column 1: [3]
Column 0: [1, 5]
Column -1: [2]
Column -2: [4]
Columns so far: {-2: [4], -1: [2], 0: [1, 5], 1: [3]}

Why: Right child is one column right of root

Step 6: Move to right child 6 of node 3 with column 2

Column 2: [6]
Column 1: [3]
Column 0: [1, 5]
Column -1: [2]
Column -2: [4]
Columns so far: {-2: [4], -1: [2], 0: [1, 5], 1: [3], 2: [6]}

Why: Right child moves one column right again

Result:

Vertical order traversal:
Column -2: 4
Column -1: 2
Column 0: 1 5
Column 1: 3
Column 2: 6

Annotated Code

DSA Rust

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

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

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

fn vertical_order_traversal(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    if root.is_none() {
        return vec![];
    }

    // Map column index to list of node values
    let mut column_table: BTreeMap<i32, Vec<i32>> = BTreeMap::new();
    // Queue for BFS: stores (node, column)
    let mut queue: VecDeque<(Box<TreeNode>, i32)> = VecDeque::new();

    queue.push_back((root.unwrap(), 0));

    while let Some((node, col)) = queue.pop_front() {
        // Add current node value to its column list
        column_table.entry(col).or_default().push(node.val);

        // If left child exists, enqueue with column - 1
        if let Some(left) = node.left {
            queue.push_back((left, col - 1));
        }

        // If right child exists, enqueue with column + 1
        if let Some(right) = node.right {
            queue.push_back((right, col + 1));
        }
    }

    // Collect results from leftmost to rightmost column
    column_table.into_iter().map(|(_col, vals)| vals).collect()
}

fn main() {
    // Build tree:
    //      1
    //     / \
    //    2   3
    //   / \   \
    //  4   5   6

    let mut root = Box::new(TreeNode::new(1));
    let mut node2 = Box::new(TreeNode::new(2));
    let mut node3 = Box::new(TreeNode::new(3));
    let node4 = Box::new(TreeNode::new(4));
    let node5 = Box::new(TreeNode::new(5));
    let node6 = Box::new(TreeNode::new(6));

    node2.left = Some(node4);
    node2.right = Some(node5);
    node3.right = Some(node6);
    root.left = Some(node2);
    root.right = Some(node3);

    let result = vertical_order_traversal(Some(root));

    for col_vals in result {
        for val in col_vals {
            print!("{} ", val);
        }
        println!();
    }
}

queue.push_back((root.unwrap(), 0));

Start BFS from root at column 0

column_table.entry(col).or_default().push(node.val);

Add current node value to its column group

if let Some(left) = node.left { queue.push_back((left, col - 1)); }

Enqueue left child with column one less

if let Some(right) = node.right { queue.push_back((right, col + 1)); }

Enqueue right child with column one more

column_table.into_iter().map(|(_col, vals)| vals).collect()

Collect columns in order from left to right

Output

4 

2 

1 5 

3 

6 

Complexity Analysis

Time: O(n) because we visit each node once during BFS

Space: O(n) for storing nodes in the queue and column map

vs Alternative: Compared to DFS, BFS naturally processes nodes top to bottom, simplifying vertical order grouping

Edge Cases

Empty tree

Returns empty list with no columns

DSA Rust

if root.is_none() { return vec![]; }

Tree with single node

Returns one column with that single node

DSA Rust

queue.push_back((root.unwrap(), 0));

Tree with multiple nodes in same column

Nodes appear in order top to bottom in that column

DSA Rust

column_table.entry(col).or_default().push(node.val);

When to Use This Pattern

When asked to print tree nodes column by column vertically, use vertical order traversal with BFS and column indexing to group nodes.

Common Mistakes

Mistake: Using DFS without tracking node levels can mix node order within columns
Fix: Use BFS to process nodes level by level ensuring top to bottom order

Mistake: Not using a sorted map for columns causes unordered output
Fix: Use a BTreeMap or equivalent to keep columns sorted from left to right

Summary

Groups binary tree nodes by vertical columns and lists them top to bottom per column.

Use when you need to print or process nodes column-wise from left to right.

Track each node's column index during BFS to maintain correct vertical order.

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