Zigzag Level Order Traversal in DSA Rust - Execution Trace

Concept Flow - Zigzag Level Order Traversal

Start at root node

↓

Initialize queue with root

↓

While queue not empty

↓

Process current level nodes

↓

Collect node values in order

↓

If level is even: left to right

↓

If level is odd: right to left

↓

Add children of current level nodes to queue

↓

Increase level count

↓

Repeat until queue empty

↓

Return zigzag order list

Traverse the tree level by level, alternating the order of node values between left-to-right and right-to-left for each level.

Execution Sample

DSA Rust

fn zigzag_level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut queue = vec![];
    let mut left_to_right = true;
    if let Some(node) = root {
        queue.push(node);
    }
    while !queue.is_empty() {
        let mut level = vec![];
        let size = queue.len();
        for _ in 0..size {
            let node = queue.remove(0);
            if left_to_right {
                level.push(node.val);
            } else {
                level.insert(0, node.val);
            }
            if let Some(left) = node.left {
                queue.push(left);
            }
            if let Some(right) = node.right {
                queue.push(right);
            }
        }
        result.push(level);
        left_to_right = !left_to_right;
    }
    result
}

This code traverses a binary tree in zigzag level order, alternating the direction of node values at each level.

Execution Table

Step	Operation	Nodes in Queue	Level Nodes Processed	Order	Level Values Collected	Queue After Processing	Visual State
1	Initialize queue with root	[1]	None	Left to Right	[]	[1]	Level 0: [1]
2	Process level 0	[1]	Node 1	Left to Right	[1]	[2,3]	Level 0: [1]
3	Add children of node 1	[2,3]	None	Left to Right	[1]	[2,3]	Level 1: [2,3]
4	Process level 1	[2,3]	Node 2	Right to Left	[2]	[3,4,5]	Level 1: [3,2]
5	Process level 1	[3,4,5]	Node 3	Right to Left	[3,2]	[4,5,6,7]	Level 1: [3,2]
6	Add children of nodes 2 and 3	[4,5,6,7]	None	Right to Left	[3,2]	[4,5,6,7]	Level 2: [4,5,6,7]
7	Process level 2	[4,5,6,7]	Node 4	Left to Right	[4]	[5,6,7]	Level 2: [4,5,6,7]
8	Process level 2	[5,6,7]	Node 5	Left to Right	[4,5]	[6,7]	Level 2: [4,5,6,7]
9	Process level 2	[6,7]	Node 6	Left to Right	[4,5,6]	[7]	Level 2: [4,5,6,7]
10	Process level 2	[7]	Node 7	Left to Right	[4,5,6,7]	[]	Level 2: [4,5,6,7]
11	Queue empty, traversal done	[]	None	N/A	[[1],[3,2],[4,5,6,7]]	[]	Final zigzag order

💡 Queue is empty, all levels processed.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	Final
queue	[1]	[2,3]	[4,5,6,7]	[]	[]
left_to_right	true	false	true	false	false
result	[]	[[1]]	[[1],[3,2]]	[[1],[3,2],[4,5,6,7]]	[[1],[3,2],[4,5,6,7]]

Key Moments - 3 Insights

Why do we insert node values at the front of the level list on odd levels?

Because on odd levels we want to collect values from right to left, so inserting at the front reverses the order. See execution_table rows 4 and 5 where level values are inserted in reverse.

Why do we use a queue to hold nodes during traversal?

The queue keeps track of nodes to process level by level. Nodes are added in order of their children, ensuring we process one level fully before moving to the next. This is shown in execution_table steps 2, 4, and 7.

How does the left_to_right variable affect traversal?

It toggles after each level to switch the order of value collection. When true, values are appended; when false, values are inserted at the front. This toggle is visible in variable_tracker and execution_table steps.

Visual Quiz - 3 Questions

Look at the execution_table, what is the order of node values collected at step 4?

A Left to Right

B Right to Left

C Random order

D No values collected

💡 Hint

Check the 'Order' column at step 4 in the execution_table.

At which step does the queue become empty, ending the traversal?

A Step 7

B Step 10

C Step 11

D Step 5

💡 Hint

Look at the 'Queue After Processing' column and the exit_note.

If left_to_right was never toggled, how would the level 1 values be collected?

A [2,3]

B [3,2]

C [1]

D Empty list

💡 Hint

Refer to variable_tracker for left_to_right changes and execution_table rows 4 and 5.

Concept Snapshot

Zigzag Level Order Traversal:
- Traverse tree level by level using a queue.
- Alternate direction each level: left-to-right, then right-to-left.
- Use a boolean flag to toggle order.
- Collect node values accordingly.
- Continue until all levels processed.

Full Transcript

Zigzag Level Order Traversal visits nodes level by level in a binary tree. It uses a queue to hold nodes of the current level. For each level, it collects node values either left to right or right to left, toggling direction after each level. Children of current nodes are added to the queue for the next level. This continues until the queue is empty, meaning all nodes have been processed. The result is a list of lists with node values in zigzag order.

Practice

1. What does Zigzag Level Order Traversal of a binary tree mean?

easy

A. Traverse nodes only from right to left at all levels

B. Traverse nodes only from left to right at all levels

C. Traverse nodes randomly without any order

D. Traverse nodes level by level, alternating direction each level

Solution

1. Step 1: Understand level order traversal

   Level order traversal means visiting nodes level by level from top to bottom.

2. Step 2: Add zigzag pattern

   Zigzag means alternating the direction of traversal at each level: left to right, then right to left, and so on.

3. Final Answer:

   Traverse nodes level by level, alternating direction each level -> Option D

4. Quick Check:

   Zigzag = alternate directions [OK]

Hint: Remember zigzag means flip direction every level [OK]

Common Mistakes:

• Thinking traversal is always left to right
• Confusing zigzag with preorder or inorder traversal
• Ignoring direction change at alternate levels

2. Which Rust data structure is best to use for implementing Zigzag Level Order Traversal?

easy

A. HashMap for storing node values

B. VecDeque for efficient front and back operations

C. BinaryHeap for priority ordering

D. LinkedList for random access

Solution

1. Step 1: Identify needed operations

   Zigzag traversal requires adding and removing nodes from both ends efficiently.

2. Step 2: Choose suitable Rust structure

   VecDeque supports push/pop from front and back efficiently, ideal for zigzag traversal.

3. Final Answer:

   VecDeque for efficient front and back operations -> Option B

4. Quick Check:

   VecDeque = double-ended queue [OK]

Hint: Use VecDeque for double-ended queue operations [OK]

Common Mistakes:

• Using HashMap which is unordered
• Using BinaryHeap which is for priority, not order
• Using LinkedList which is inefficient in Rust

3. What is the output of the zigzag level order traversal for this tree?

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Traverse level 0 left to right

   Level 0 nodes: [1]

2. Step 2: Traverse level 1 right to left

   Level 1 nodes: [3, 2]

3. Step 3: Traverse level 2 left to right

   Level 2 nodes: [4, 5, 6]

4. Final Answer:

   [[1], [3, 2], [6, 5, 4]] -> Option A

5. Quick Check:

   Zigzag levels alternate direction [OK]

Hint: Alternate direction each level when listing nodes [OK]

Common Mistakes:

• Not reversing order on alternate levels
• Mixing node values in wrong order
• Ignoring missing children in traversal

4. Given this Rust code snippet for zigzag traversal, what is the bug?

let mut left_to_right = true;
while !queue.is_empty() {
    let level_size = queue.len();
    let mut level_nodes = Vec::new();
    for _ in 0..level_size {
        let node = queue.pop_front().unwrap();
        if left_to_right {
            level_nodes.push(node.val);
        } else {
            level_nodes.insert(0, node.val);
        }
        if let Some(left) = node.left {
            queue.push_back(left);
        }
        if let Some(right) = node.right {
            queue.push_back(right);
        }
    }
    left_to_right = !left_to_right;
}

medium

A. Inserting at index 0 in Vec is inefficient; use a deque instead

B. The queue should be cleared each iteration

C. left_to_right flag is never toggled

D. Nodes are pushed to queue incorrectly

Solution

1. Step 1: Analyze insertion in level_nodes

   Inserting at index 0 in a Vec shifts all elements, causing inefficiency.

2. Step 2: Suggest better data structure

   Using a VecDeque allows efficient push_front operations for reverse order.

3. Final Answer:

   Inserting at index 0 in Vec is inefficient; use a deque instead -> Option A

4. Quick Check:

   Vec insert(0) is slow; VecDeque better [OK]

Hint: Avoid Vec insert(0); prefer VecDeque for front insertions [OK]

Common Mistakes:

• Thinking queue needs clearing each level
• Missing toggle of left_to_right flag
• Incorrectly pushing children nodes

5. How would you modify a zigzag level order traversal to return the sum of values at each level instead of nodes themselves?

hard

A. Use a stack instead of queue to store nodes

B. Add node values directly to a global sum without level separation

C. Sum values in level_nodes vector before adding to result

D. Reverse the tree before traversal

Solution

1. Step 1: Collect node values per level

   During traversal, store node values in a temporary vector for each level.

2. Step 2: Calculate sum of level nodes

   Sum all values in the vector before adding the sum to the final result list.

3. Final Answer:

   Sum values in level_nodes vector before adding to result -> Option C

4. Quick Check:

   Sum per level = sum(level_nodes) [OK]

Hint: Sum nodes per level before storing result [OK]

Common Mistakes:

• Summing all nodes without level grouping
• Using stack breaks level order logic
• Reversing tree changes structure, not traversal