Vertical Order Traversal of Binary Tree in DSA Rust - Execution Trace

Concept Flow - Vertical Order Traversal of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for BFS traversal

↓

Dequeue node

↓

Record node value at its horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort keys (horizontal distances)

↓

Output nodes grouped by horizontal distance

Traverse the tree level by level, track horizontal distances, group nodes by these distances, then output groups from left to right.

Execution Sample

DSA Rust

fn vertical_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    use std::collections::{HashMap, VecDeque};
    let mut map = HashMap::new();
    let mut queue = VecDeque::new();
    if let Some(node) = root {
        queue.push_back((node, 0));
    }
    // BFS traversal
}

This code starts a breadth-first search on the tree, tracking each node's horizontal distance.

Execution Table

Step	Operation	Node Visited	Horizontal Distance (hd)	Map State (hd -> nodes)	Queue State	Visual State
1	Start BFS	Root(1)	0	{0:[1]}	[(2, -1), (3, 1)]	1(0) / \ 2(-1) 3(1)
2	Dequeue node	2	-1	{0:[1], -1:[2]}	[(3, 1), (4, -2), (5, 0)]	1(0) / \ 2(-1) 3(1) / 4(-2) 5(0)
3	Dequeue node	3	1	{0:[1], -1:[2], 1:[3]}	[(4, -2), (5, 0), (6, 0), (7, 2)]	1(0) / \ 2(-1) 3(1) / 4(-2) 5(0) \ 6(0) \ 7(2)
4	Dequeue node	4	-2	{0:[1], -1:[2], 1:[3], -2:[4]}	[(5, 0), (6, 0), (7, 2)]	1(0) / \ 2(-1) 3(1) / 4(-2) 5(0) \ 6(0) \ 7(2)
5	Dequeue node	5	0	{0:[1,5], -1:[2], 1:[3], -2:[4]}	[(6, 0), (7, 2)]	1(0) / \ 2(-1) 3(1) / 4(-2) 5(0) \ 6(0) \ 7(2)
6	Dequeue node	6	0	{0:[1,5,6], -1:[2], 1:[3], -2:[4]}	[(7, 2)]	1(0) / \ 2(-1) 3(1) / 4(-2) 5(0) \ 6(0) \ 7(2)
7	Dequeue node	7	2	{0:[1,5,6], -1:[2], 1:[3], -2:[4], 2:[7]}	[]	1(0) / \ 2(-1) 3(1) / 4(-2) 5(0) \ 6(0) \ 7(2)
8	Queue empty	None	N/A	Final grouping	Empty	Traversal complete

💡 Queue is empty, all nodes visited and grouped by horizontal distance.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
queue	[(1,0)]	[(2,-1),(3,1)]	[(3,1),(4,-2),(5,0)]	[(4,-2),(5,0),(6,0),(7,2)]	[(5,0),(6,0),(7,2)]	[(6,0),(7,2)]	[(7,2)]	[]	[]
map	{}	{0:[1]}	{0:[1], -1:[2]}	{0:[1], -1:[2], 1:[3]}	{0:[1], -1:[2], 1:[3], -2:[4]}	{0:[1,5], -1:[2], 1:[3], -2:[4]}	{0:[1,5,6], -1:[2], 1:[3], -2:[4]}	{0:[1,5,6], -1:[2], 1:[3], -2:[4], 2:[7]}	{0:[1,5,6], -1:[2], 1:[3], -2:[4], 2:[7]}

Key Moments - 3 Insights

Why do we assign horizontal distance (hd) and how does it help?

Assigning hd helps group nodes vertically. Nodes with same hd are in the same vertical line. See execution_table rows 1-7 where nodes are added to map by hd.

Why do we use a queue and BFS instead of DFS?

BFS ensures nodes are processed level by level, preserving top-to-bottom order in vertical lines. This is shown in execution_table where nodes are dequeued in BFS order.

What happens if a node has no left or right child?

No new nodes are enqueued for missing children, so queue size decreases until empty. See execution_table steps where queue shrinks after leaf nodes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what nodes are in the map at horizontal distance 0?

A [1, 5]

B [5]

C [1]

D [1, 3]

💡 Hint

Check the 'Map State' column at Step 3 in execution_table.

At which step does the queue become empty?

A Step 7

B Step 8

C Step 6

D Step 5

💡 Hint

Look at the 'Queue State' column and find when it shows empty.

If the root node had no right child, how would the queue state change after Step 1?

A Queue would have only left child with hd -1

B Queue would be empty

C Queue would have left and right child with hd 0

D Queue would have right child with hd 1

💡 Hint

Refer to Step 1 queue state and consider missing right child.

Concept Snapshot

Vertical Order Traversal:
- Assign horizontal distance (hd) to nodes: root=0, left=hd-1, right=hd+1
- Use BFS with queue to visit nodes level-wise
- Store nodes in map keyed by hd
- After traversal, sort keys and output grouped nodes
- Preserves vertical and top-to-bottom order

Full Transcript

Vertical Order Traversal visits a binary tree level by level, tracking each node's horizontal distance from the root. Nodes are grouped by these distances to form vertical lines. We use a queue for breadth-first search, enqueueing left children with hd-1 and right children with hd+1. After visiting all nodes, we sort the horizontal distances and output nodes grouped by these distances, preserving vertical order from left to right and top to bottom.

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