Zigzag Level Order Traversal in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Level Order Traversal on a Balanced Tree

What is the output of the zigzag level order traversal for the given binary tree?

DSA Rust

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn zigzag_level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    if root.is_none() {
        return results;
    }
    let mut current_level = VecDeque::new();
    current_level.push_back(root.unwrap());
    let mut left_to_right = true;

    while !current_level.is_empty() {
        let mut level_size = current_level.len();
        let mut level_nodes = Vec::new();
        let mut next_level = VecDeque::new();

        while level_size > 0 {
            let node = if left_to_right {
                current_level.pop_front().unwrap()
            } else {
                current_level.pop_back().unwrap()
            };
            level_nodes.push(node.val);

            if left_to_right {
                if let Some(left) = node.left {
                    next_level.push_back(left);
                }
                if let Some(right) = node.right {
                    next_level.push_back(right);
                }
            } else {
                if let Some(right) = node.right {
                    next_level.push_front(right);
                }
                if let Some(left) = node.left {
                    next_level.push_front(left);
                }
            }
            level_size -= 1;
        }
        results.push(level_nodes);
        current_level = next_level;
        left_to_right = !left_to_right;
    }
    results
}

fn main() {
    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: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 7, left: None, right: None })),
        })),
    }));
    let result = zigzag_level_order(root);
    println!("{:?}", result);
}

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

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

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

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

💡 Hint

Remember that zigzag means alternating the direction of traversal at each level.

The traversal starts left to right on level 1, then right to left on level 2, then left to right on level 3, and so on.

So level 1: [1]

Level 2: [3, 2] (reverse order)

Level 3: [4, 5, 6, 7]

🧠 Conceptual

intermediate

Understanding the Data Structure Used in Zigzag Traversal

Which data structure is most suitable to implement zigzag level order traversal efficiently and why?

A Deque, because it supports insertion and removal from both ends, enabling alternating traversal directions.

B Stack, because it allows LIFO order traversal which is needed for zigzag.

C Queue, because it allows FIFO order traversal of nodes level by level.

D HashMap, because it stores nodes with their levels as keys for quick access.

💡 Hint

Think about how to efficiently switch directions at each level.

A deque (double-ended queue) allows adding and removing nodes from both front and back, which is essential to alternate the traversal direction at each level without extra overhead.

🔧 Debug

advanced

Identify the Bug in Zigzag Traversal Code

Given the following Rust code snippet for zigzag traversal, what error will it produce when run?

DSA Rust

fn zigzag_level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    if root.is_none() {
        return results;
    }
    let mut current_level = VecDeque::new();
    current_level.push_back(root.unwrap());
    let mut left_to_right = true;

    while !current_level.is_empty() {
        let mut level_size = current_level.len();
        let mut level_nodes = Vec::new();
        let mut next_level = VecDeque::new();

        while level_size > 0 {
            let node = if left_to_right {
                current_level.pop_front().unwrap()
            } else {
                current_level.pop_back().unwrap()
            };
            level_nodes.push(node.val);

            // Bug: next_level is not defined or updated
            if left_to_right {
                if let Some(left) = node.left {
                    next_level.push_back(left);
                }
                if let Some(right) = node.right {
                    next_level.push_back(right);
                }
            } else {
                if let Some(right) = node.right {
                    next_level.push_front(right);
                }
                if let Some(left) = node.left {
                    next_level.push_front(left);
                }
            }
            level_size -= 1;
        }
        results.push(level_nodes);
        current_level = next_level;
        left_to_right = !left_to_right;
    }
    results
}

A Runtime panic: unwrap on None when popping from empty VecDeque.

B Logical error: traversal direction does not alternate correctly.

C Compile-time error: 'next_level' is not declared in this scope.

D No error, code runs correctly and returns expected output.

💡 Hint

Check variable declarations inside the loop.

The variable 'next_level' is used but never declared or initialized, causing a compile-time error.

🚀 Application

advanced

Zigzag Traversal Output for an Unbalanced Tree

What is the zigzag level order traversal output for this unbalanced binary tree? Tree structure: - Root: 10 - Left child: 5 - Left child of 5: 3 - Right child of 5: 7 - Right child of root: 15 - Right child of 15: 18

A [[10], [15, 5], [3, 7, 18]]

B [[10], [5, 15], [18, 7, 3]]

C [[10], [15, 5], [18, 7, 3]]

D [[10], [5, 15], [3, 7, 18]]

💡 Hint

Remember to alternate direction at each level.

Level 1: left to right → [10]

Level 2: right to left → [15, 5]

Level 3: left to right → [3, 7, 18]

❓ Predict Output

expert

Output of Zigzag Traversal with Single Node Tree

What is the output of the zigzag level order traversal for a tree with only one node valued 42?

DSA Rust

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn zigzag_level_order(root: Option<Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut results = Vec::new();
    if root.is_none() {
        return results;
    }
    let mut current_level = VecDeque::new();
    current_level.push_back(root.unwrap());
    let mut left_to_right = true;

    while !current_level.is_empty() {
        let mut level_size = current_level.len();
        let mut level_nodes = Vec::new();
        let mut next_level = VecDeque::new();

        while level_size > 0 {
            let node = if left_to_right {
                current_level.pop_front().unwrap()
            } else {
                current_level.pop_back().unwrap()
            };
            level_nodes.push(node.val);

            if left_to_right {
                if let Some(left) = node.left {
                    next_level.push_back(left);
                }
                if let Some(right) = node.right {
                    next_level.push_back(right);
                }
            } else {
                if let Some(right) = node.right {
                    next_level.push_front(right);
                }
                if let Some(left) = node.left {
                    next_level.push_front(left);
                }
            }
            level_size -= 1;
        }
        results.push(level_nodes);
        current_level = next_level;
        left_to_right = !left_to_right;
    }
    results
}

fn main() {
    let root = Some(Box::new(TreeNode { val: 42, left: None, right: None }));
    let result = zigzag_level_order(root);
    println!("{:?}", result);
}

A [[], [42]]

B []

C [[42], []]

D [[42]]

💡 Hint

A single node tree has only one level.

Since there is only one node, the traversal returns a single level with that node's value.

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