Zigzag Level Order Traversal in DSA Rust - Build from Scratch

Zigzag Level Order Traversal

📖 Scenario: You are working with a binary tree that represents a company's organizational chart. You want to list the employees level by level, but with a twist: the order of listing alternates between left-to-right and right-to-left for each level. This zigzag pattern helps visualize the hierarchy in a more dynamic way.

🎯 Goal: Build a Rust program that performs a zigzag level order traversal on a binary tree. The program will output the values of nodes level by level, alternating the direction of traversal at each level.

📋 What You'll Learn

Create a binary tree structure with nodes containing integer values

Use a queue to traverse the tree level by level

Alternate the order of node values between left-to-right and right-to-left for each level

Print the final zigzag level order traversal as a vector of vectors

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in scenarios like displaying hierarchical data with alternating directions for better readability, such as organizational charts or UI tree views.

💼 Career

Understanding tree traversals and queue usage is fundamental for software engineering roles involving data structures, algorithms, and system design.

1

Create the binary tree structure and build the sample tree

Define a struct called TreeNode with fields val: i32, left: Option>, and right: Option>. Then create a variable called root representing this exact tree:

1
/ \ 2 3
/ \ \ 4 5 6

DSA Rust

# Define the TreeNode struct and create the root node
# Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Create a queue and a variable to track traversal direction

Create a mutable variable called queue as a VecDeque and initialize it with root.clone(). Also create a mutable boolean variable called left_to_right and set it to true to track the zigzag direction.

DSA Rust

struct TreeNode {
    val: i32,
    left: Option>,
    right: Option>,
}

let root = Some(Box::new(TreeNode {
    val: 1,
    left: Some(Box::new(TreeNode {
        val: 2,
        left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
        right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
    })),
    right: Some(Box::new(TreeNode {
        val: 3,
        left: None,
        right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
    })),
}));

// Create queue and left_to_right variables
# Your code here

Hint

Use VecDeque from std::collections for efficient queue operations.

3

Implement the zigzag level order traversal logic

Write a while loop that runs while queue is not empty. Inside, create a vector level_vals to store current level values. Use a for loop to process all nodes currently in queue. For each node, push its children into queue. After collecting values, if left_to_right is false, reverse level_vals. Toggle left_to_right at the end of each level. Store each level_vals vector into a result vector of vectors.

DSA Rust

use std::collections::VecDeque;

struct TreeNode {
    val: i32,
    left: Option>,
    right: Option>,
}

let root = Some(Box::new(TreeNode {
    val: 1,
    left: Some(Box::new(TreeNode {
        val: 2,
        left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
        right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
    })),
    right: Some(Box::new(TreeNode {
        val: 3,
        left: None,
        right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
    })),
}));

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

let mut result: Vec> = Vec::new()

// Implement zigzag traversal logic here
# Your code here

Hint

Use queue.len() to get the number of nodes at the current level. Use pop_front() to dequeue nodes. Clone children before pushing to queue.

4

Print the zigzag level order traversal result

Write a println! statement to print the result vector of vectors.

DSA Rust

use std::collections::VecDeque;

struct TreeNode {
    val: i32,
    left: Option>,
    right: Option>,
}

let root = Some(Box::new(TreeNode {
    val: 1,
    left: Some(Box::new(TreeNode {
        val: 2,
        left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
        right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
    })),
    right: Some(Box::new(TreeNode {
        val: 3,
        left: None,
        right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
    })),
}));

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

let mut result: Vec> = Vec::new();

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

    for _ in 0..level_size {
        if let Some(Some(node)) = queue.pop_front() {
            level_vals.push(node.val);
            if node.left.is_some() {
                queue.push_back(node.left.clone());
            }
            if node.right.is_some() {
                queue.push_back(node.right.clone());
            }
        }
    }

    if !left_to_right {
        level_vals.reverse();
    }

    result.push(level_vals);
    left_to_right = !left_to_right;
}

// Print the result
# Your code here

Hint

Use println!("{:?}", result); to print the vector of vectors.

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