Zigzag Level Order Traversal in DSA C# - Execution Trace

Concept Flow - Zigzag Level Order Traversal

Start at root node

↓

Initialize queue with root

↓

While queue not empty

↓

Process all nodes at current level

↓

Collect node values in order

↓

If level is even: left to right

↓

Add children to queue

↓

Increase level count

↩Back to While queue not empty

Start from the root, process nodes level by level, alternate the order of values collected each level, and add children for next level.

Execution Sample

DSA C#

public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
  var results = new List<IList<int>>();
  if (root == null) return results;
  var queue = new Queue<TreeNode>();
  queue.Enqueue(root);
  bool leftToRight = true;
  while (queue.Count > 0) {
    int size = queue.Count;
    var level = new List<int>();
    for (int i = 0; i < size; i++) {
      var node = queue.Dequeue();
      if (leftToRight) level.Add(node.val);
      else level.Insert(0, node.val);
      if (node.left != null) queue.Enqueue(node.left);
      if (node.right != null) queue.Enqueue(node.right);
    }
    results.Add(level);
    leftToRight = !leftToRight;
  }
  return results;
}

Traverse the tree level by level, alternating the order of node values collected at each level.

Execution Table

Step	Operation	Nodes in Queue	Level Nodes Collected	Order	Visual State of Level	Queue After Step
1	Start with root node 1	[1]	[]	Left to Right	[]	[1]
2	Dequeue node 1, add value	[]	[1]	Left to Right	[1]	[2,3]
3	Enqueue children 2 and 3	[2,3]	[1]	Left to Right	[1]	[2,3]
4	Add level [1] to results	[2,3]	[1]	Left to Right	[1]	[2,3]
5	Toggle order to Right to Left	[2,3]	[]	Right to Left	[]	[2,3]
6	Dequeue node 2, add value at front	[3]	[2]	Right to Left	[2]	[3,4,5]
7	Enqueue children 4 and 5	[3,4,5]	[2]	Right to Left	[2]	[3,4,5]
8	Dequeue node 3, add value at front	[4,5]	[3,2]	Right to Left	[3,2]	[4,5,6,7]
9	Enqueue children 6 and 7	[4,5,6,7]	[3,2]	Right to Left	[3,2]	[4,5,6,7]
10	Add level [3,2] to results	[4,5,6,7]	[3,2]	Right to Left	[3,2]	[4,5,6,7]
11	Toggle order to Left to Right	[4,5,6,7]	[]	Left to Right	[]	[4,5,6,7]
12	Dequeue node 4, add value	[5,6,7]	[4]	Left to Right	[4]	[5,6,7]
13	Dequeue node 5, add value	[6,7]	[4,5]	Left to Right	[4,5]	[6,7]
14	Dequeue node 6, add value	[7]	[4,5,6]	Left to Right	[4,5,6]	[7]
15	Dequeue node 7, add value	[]	[4,5,6,7]	Left to Right	[4,5,6,7]	[]
16	Add level [4,5,6,7] to results	[]	[4,5,6,7]	Left to Right	[4,5,6,7]	[]
17	Queue empty, traversal ends	[]	[]	-	-	[]

💡 Queue is empty, all levels processed.

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 15	Final
queue	[1]	[2,3]	[4,5,6,7]	[]	[]
leftToRight	true	true	false	true	false
level	[]	[1]	[3,2]	[4,5,6,7]	[]
results	[]	[]	[[1]]	[[1],[3,2]]	[[1],[3,2],[4,5,6,7]]

Key Moments - 3 Insights

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

Because on odd levels we want to collect values in right-to-left order, inserting at the front reverses the order as nodes are dequeued left to right (see execution_table rows 6 and 8).

Why do we toggle the 'leftToRight' flag after processing each level?

Toggling 'leftToRight' changes the order of value collection for the next level, ensuring zigzag pattern (see execution_table rows 5, 10, and 11).

How does the queue help in level order traversal?

The queue holds nodes of the current level and their children for the next level, allowing us to process nodes level by level (see variable_tracker 'queue' changes).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the order of values collected in the current level?

A Right to Left

B Random order

C Left to Right

D No values collected yet

💡 Hint

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

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

A Step 16

B Step 17

C Step 15

D Step 14

💡 Hint

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

If we did not toggle 'leftToRight', how would the levels be collected?

A All levels right to left

B Alternate levels reversed

C All levels left to right

D No values collected

💡 Hint

See variable_tracker 'leftToRight' changes and their effect on 'level' collection.

Concept Snapshot

Zigzag Level Order Traversal:
- Use a queue for level order traversal.
- Collect node values level by level.
- Alternate order: left-to-right, then right-to-left.
- Insert values at front for right-to-left levels.
- Toggle direction after each level.
- Continue until queue is empty.

Full Transcript

Zigzag Level Order Traversal visits nodes level by level in a binary tree. We start with the root node in a queue. For each level, we process all nodes currently in the queue. We collect their values in a list. On even levels, we add values left to right. On odd levels, we add values right to left by inserting at the front of the list. We enqueue the children of each node for the next level. After finishing a level, we toggle the direction for the next level. This continues until the queue is empty, meaning all nodes have been processed. The result is a list of lists, each representing a level's values in zigzag order.

Practice

1. What does the Zigzag Level Order Traversal of a binary tree do differently compared to a normal level order traversal?

easy

A. It alternates the direction of traversal at each level, left to right then right to left.

B. It visits nodes only on the left subtree.

C. It visits nodes in reverse order of their insertion.

D. It traverses nodes randomly without any order.

Solution

1. Step 1: Understand normal level order traversal

   Normal level order traversal visits nodes level by level from left to right.

2. Step 2: Identify zigzag difference

   Zigzag traversal alternates direction each level: first left to right, then right to left, and so on.

3. Final Answer:

   It alternates the direction of traversal at each level, left to right then right to left. -> Option A

4. Quick Check:

   Zigzag = alternate directions [OK]

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

Common Mistakes:

• Thinking it only visits left subtree
• Assuming traversal is always left to right
• Confusing zigzag with reverse order

2. Which of the following C# code snippets correctly initializes a queue to perform a zigzag level order traversal?

easy

A. List<TreeNode> queue = new List<TreeNode>();

B. Queue<TreeNode> queue = new Queue<TreeNode>();

C. Stack<TreeNode> queue = new Stack<TreeNode>();

D. Dictionary queue = new Dictionary();

Solution

1. Step 1: Identify data structure for BFS

   Queue is used for breadth-first search to process nodes level by level.

2. Step 2: Check code snippet correctness

   Queue<TreeNode> queue = new Queue<TreeNode>(); correctly declares a Queue of TreeNode objects, suitable for traversal.

3. Final Answer:

   Queue<TreeNode> queue = new Queue<TreeNode>(); -> Option B

4. Quick Check:

   Queue for BFS = Queue<TreeNode> queue = new Queue<TreeNode>(); [OK]

Hint: Use Queue for level order traversal in C# [OK]

Common Mistakes:

• Using Stack instead of Queue for BFS
• Using List which lacks FIFO behavior
• Using Dictionary which is not suitable here

3. Given the binary tree:

    1
   / \
  2   3
 / \   \
4   5   6

What is the output of zigzag level order traversal?

medium

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

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

C. [[1], [3, 2], [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: [2, 3], reversed to [3, 2]

3. Step 3: Traverse level 2 left to right

   Level 2 nodes: [4, 5, 6]

4. Final Answer:

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

5. Quick Check:

   Zigzag levels = [[1], [3, 2], [4, 5, 6]] [OK]

Hint: Alternate direction each level, reverse nodes on odd levels [OK]

Common Mistakes:

• Not reversing nodes on alternate levels
• Mixing node order in last level
• Confusing left and right child order

4. Consider this C# code snippet for zigzag traversal:

if (level % 2 == 0)
    result.Add(currentLevel);
else
    result.Add(currentLevel.Reverse().ToList());

What is the bug in this code?

medium

A. It reverses the list on even levels instead of odd levels.

B. It reverses the list on odd levels instead of even levels.

C. It reverses the original list causing side effects.

D. It does not reverse the list at all.

Solution

1. Step 1: Understand zigzag pattern

   Zigzag reverses nodes on odd levels (1, 3, 5...), not even levels (0, 2, 4...).

2. Step 2: Analyze code condition

   The condition correctly identifies even/odd levels for reversal.

3. Step 3: Identify the actual issue

   currentLevel.Reverse() (List<TreeNode>.Reverse) modifies the list in place and returns void, causing side effects and a compilation error on .ToList().

4. Final Answer:

   It reverses the original list causing side effects. -> Option C

5. Quick Check:

   List.Reverse() in-place modifies original [OK]

Hint: Reverse nodes only on odd levels (1, 3, 5...) [OK]

Common Mistakes:

• Reversing on even levels instead of odd
• Modifying original list causing bugs
• Not reversing at all

5. You want to perform zigzag level order traversal on a binary tree but only collect nodes with even values. Which modification is best to apply?

hard

A. Use a stack instead of a queue to collect only even nodes.

B. Reverse the entire result list after traversal to get even nodes first.

C. Skip reversing on odd levels to keep order consistent for even nodes.

D. Filter nodes by even value before adding them to the current level list during traversal.

Solution

1. Step 1: Identify filtering requirement

   We want only even-valued nodes in the output, so filter nodes during traversal.

2. Step 2: Apply filtering during level collection

   Filter nodes by checking if value is even before adding to current level list.

3. Step 3: Keep zigzag logic intact

   After filtering, apply zigzag reversal as usual on filtered nodes.

4. Final Answer:

   Filter nodes by even value before adding them to the current level list during traversal. -> Option D

5. Quick Check:

   Filter during traversal = Filter nodes by even value before adding them to the current level list during traversal. [OK]

Hint: Filter nodes while collecting each level, then zigzag [OK]

Common Mistakes:

• Reversing entire result instead of filtering
• Skipping reversal breaks zigzag pattern
• Using stack incorrectly for filtering