Zigzag Level Order Traversal in DSA Rust

Mental Model

We visit nodes level by level, but alternate the direction of reading each level to create a zigzag pattern.

Analogy: Imagine reading lines of text where the first line is read left to right, the next line right to left, then left to right again, like a snake moving back and forth.

       1
      / \
     2   3
    / \   \
   4   5   6

Level 0: 1 (left to right)
Level 1: 3 -> 2 (right to left)
Level 2: 4 -> 5 -> 6 (left to right)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3 -> 4, 5, null, 6 (root 1, left 2, right 3, 2's children 4 and 5, 3's right child 6)

Goal: Traverse the tree level by level, alternating direction each level to get zigzag order

Step 1: Start at root level (level 0), direction left to right

Level 0: [1]
Output: [[1]]

Why: We begin traversal from the root node, reading left to right

Step 2: Move to level 1, direction right to left

Level 1 nodes: 2 -> 3
Output: [[1], [3, 2]]

Why: We reverse the order of nodes at level 1 to get zigzag pattern

Step 3: Move to level 2, direction left to right

Level 2 nodes: 4 -> 5 -> 6
Output: [[1], [3, 2], [4, 5, 6]]

Why: We switch direction back to left to right for level 2

Result:

Final zigzag order: [[1], [3, 2], [4, 5, 6]]

Annotated Code

DSA Rust

use std::collections::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 zigzag_level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    if root.is_none() {
        return results;
    }

    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());
    let mut left_to_right = true;

    while !queue.is_empty() {
        let level_size = queue.len();
        let mut level_nodes = Vec::with_capacity(level_size);

        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);
            }
        }

        results.push(level_nodes);
        left_to_right = !left_to_right; // switch direction
    }

    results
}

fn main() {
    // Construct the 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 = zigzag_level_order(Some(root));
    println!("{:?}", result);
}

if root.is_none() { return results; }

handle empty tree early to avoid processing

queue.push_back(root.unwrap());

start BFS with root node in queue

while !queue.is_empty() {

process nodes level by level until queue is empty

for _ in 0..level_size {

iterate over all nodes in current level

if left_to_right { level_nodes.push(node.val); } else { level_nodes.insert(0, node.val); }

append or prepend node value depending on current direction

if let Some(left) = node.left { queue.push_back(left); }

enqueue left child if exists

if let Some(right) = node.right { queue.push_back(right); }

enqueue right child if exists

left_to_right = !left_to_right;

flip direction for next level

Output

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

Complexity Analysis

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

Space: O(n) because the queue and result store nodes at each level

vs Alternative: Compared to normal level order traversal, zigzag adds a small overhead for reversing order but still remains O(n)

Edge Cases

Empty tree

Returns empty list immediately

DSA Rust

if root.is_none() { return results; }

Single node tree

Returns list with one level containing the single node

DSA Rust

queue.push_back(root.unwrap());

Tree with only left or only right children

Traverses levels correctly alternating direction even if some children are missing

DSA Rust

if let Some(left) = node.left { queue.push_back(left); }

When to Use This Pattern

When a problem asks for level order traversal but with alternating directions per level, use zigzag level order traversal to handle the direction switch cleanly.

Common Mistakes

Mistake: Always appending nodes without reversing order on alternate levels
Fix: Insert nodes at the front of the level list on alternate levels to reverse order

Mistake: Not toggling the direction flag after each level
Fix: Flip the left_to_right boolean after processing each level

Summary

Traverses a binary tree level by level, alternating the order of nodes each level to create a zigzag pattern.

Use when you need to read tree nodes in a back-and-forth manner level-wise.

The key is to switch the direction of node insertion at each level to achieve 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