Vertical Order Traversal of Binary Tree in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Vertical Order Traversal of a Binary Tree?

It is a way to print the nodes of a binary tree column by column, from left to right. Nodes in the same vertical line are grouped together.

beginner

How do we assign horizontal distances to nodes in Vertical Order Traversal?

The root node is assigned horizontal distance 0. Left child nodes get horizontal distance -1 from their parent, right child nodes get +1.

intermediate

Why do we use a map or dictionary in Vertical Order Traversal?

To group nodes by their horizontal distance. The map key is the horizontal distance, and the value is a list of nodes at that distance.

intermediate

What data structure is commonly used to perform the traversal for Vertical Order Traversal?

A queue is used for level order traversal (BFS) while tracking horizontal distances of nodes.

beginner

How do we print the final Vertical Order Traversal result?

We print nodes grouped by horizontal distance from smallest to largest, showing columns from left to right.

What horizontal distance is assigned to the root node in Vertical Order Traversal?

A 1

B Depends on tree height

C -1

D 0

The root node is always assigned horizontal distance 0.

Which data structure helps group nodes by their vertical columns?

A Linked List

B Stack

C Map or Dictionary

D Array

A map or dictionary groups nodes by their horizontal distance keys.

How is the horizontal distance of a right child node related to its parent?

A Parent's distance - 1

B Parent's distance + 1

C Same as parent

D Depends on node value

Right child nodes have horizontal distance one more than their parent.

Which traversal method is commonly used to visit nodes for Vertical Order Traversal?

A Level Order Traversal (BFS)

B Preorder Traversal

C Depth First Search

D Postorder Traversal

Level order traversal (BFS) is used to visit nodes while tracking horizontal distances.

In the final output, how are vertical columns ordered?

A From left to right

B From top to bottom

C Random order

D From right to left

Columns are printed from left (smallest horizontal distance) to right (largest).

Explain how to perform Vertical Order Traversal of a binary tree step-by-step.

Think about how to visit nodes and keep track of their vertical positions.

Describe why a queue and a map are important in Vertical Order Traversal.

Consider how to organize nodes by their vertical position while visiting them.

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