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 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

We start from the root, use a queue to process nodes level by level, collecting values in zigzag order by reversing the order on odd levels.

Execution Sample

DSA C

void zigzagTraversal(TreeNode* root) {
  if (!root) return;
  queue<TreeNode*> q;
  q.push(root);
  int level = 0;
  while (!q.empty()) {
    int size = q.size();
    vector<int> levelNodes;
    for (int i = 0; i < size; i++) {
      TreeNode* node = q.front(); q.pop();
      levelNodes.push_back(node->val);
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    if (level % 2 == 1) reverse(levelNodes.begin(), levelNodes.end());
    printLevel(levelNodes);
    level++;
  }
}

This code visits each tree level, collects node values, reverses order on odd levels, and prints them.

Execution Table

Step	Operation	Nodes in Queue	Level	Level Nodes Collected	Order Applied	Visual State
1	Initialize queue with root (1)	[1]	0	[]	N/A	Queue: [1]
2	Process level 0	[1]	0	[1]	Left to Right	Output: [1]
3	Add children of 1 (2,3)	[2,3]	1	[]	N/A	Queue: [2,3]
4	Process level 1	[2,3]	1	[2,3]	Right to Left	Output: [3,2]
5	Add children of 2 (4,5) and 3 (6,7)	[4,5,6,7]	2	[]	N/A	Queue: [4,5,6,7]
6	Process level 2	[4,5,6,7]	2	[4,5,6,7]	Left to Right	Output: [4,5,6,7]
7	Add children of 4,5,6,7 (none)	[]	3	[]	N/A	Queue empty, traversal ends

💡 Queue is empty after processing all levels, traversal complete.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
queue	[1]	[2,3]	[4,5,6,7]	[]	[]
level	0	1	2	3	3
levelNodes	[]	[1]	[3,2]	[4,5,6,7]	[]

Key Moments - 3 Insights

Why do we reverse the level nodes only on odd levels?

Because zigzag means alternating directions: even levels go left to right, odd levels right to left. See execution_table rows 4 and 6 where reversal happens only at level 1.

Why do we add children to the queue after processing the entire current level?

To ensure we process nodes level by level. Adding children after collecting all current level nodes keeps the queue organized by levels. See execution_table rows 3 and 5.

What happens when the queue becomes empty?

It means all nodes have been processed and traversal ends. See execution_table row 7 where queue is empty and traversal stops.

Visual Quiz - 3 Questions

Look at the execution_table, what is the queue content after processing level 1?

A [4,5,6,7]

B [2,3]

C [1]

D []

💡 Hint

Check the 'Nodes in Queue' column after Step 5 in execution_table.

At which level does the traversal reverse the order of nodes?

A Level 0

B Level 1

C Level 2

D Level 3

💡 Hint

Look at the 'Order Applied' column in execution_table rows 2,4,6.

If the root had no children, what would be the final queue state after step 2?

A Empty queue []

B [1]

C [null]

D [2,3]

💡 Hint

Refer to variable_tracker 'queue' values and execution_table step 7 where queue empties after no children.

Concept Snapshot

Zigzag Level Order Traversal:
- Use a queue to traverse tree level by level.
- Collect nodes values per level.
- Reverse order on odd levels for zigzag effect.
- Add children after processing current level.
- Stop when queue is empty.

Full Transcript

Zigzag Level Order Traversal visits tree nodes level by level, alternating the order of node values between left-to-right and right-to-left on each level. We start with the root node in a queue. For each level, we process all nodes currently in the queue, collect their values, and add their children to the queue for the next level. On even levels, we keep the order left to right; on odd levels, we reverse the order to right to left. This continues until the queue is empty, meaning all nodes have been visited. The execution table shows the queue contents, level number, collected nodes, and the order applied at each step. The variable tracker shows how the queue, level count, and collected nodes change over time. Key moments clarify why reversal happens only on odd levels, why children are added after processing a level, and when traversal ends. The visual quiz tests understanding of queue state, reversal levels, and empty queue scenarios.

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 traverses the tree in preorder fashion.

B. It visits nodes only at even levels.

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

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

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 changes direction at each level, so first level left to right, next 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 D

4. Quick Check:

   Zigzag alternates direction = It alternates the direction of traversal at each level, left to right then right to left. [OK]

Hint: Remember zigzag flips direction each level [OK]

Common Mistakes:

• Thinking it only visits even levels
• Confusing with preorder traversal
• Assuming it visits nodes in insertion order

2. Which of the following C code snippets correctly initializes a queue for level order traversal in Zigzag Level Order Traversal?

easy

A. Queue q; q.front = 0; q.rear = 0;

B. Queue* q = createQueue(); q->front = q->rear = -1;

C. Queue* q; q->front = 0; q->rear = 0;

D. Queue q = NULL; q->front = -1; q->rear = -1;

Solution

1. Step 1: Understand queue initialization in C

   Queue pointer must be assigned memory using createQueue() or malloc before accessing members.

2. Step 2: Check each option

   Queue* q = createQueue(); q->front = q->rear = -1; correctly creates a queue pointer and initializes front and rear to -1. Queue q; q.front = 0; q.rear = 0; uses struct without pointer but does not allocate memory. Queue* q; q->front = 0; q->rear = 0; uses pointer without allocation. Queue q = NULL; q->front = -1; q->rear = -1; assigns NULL to struct variable which is invalid.

3. Final Answer:

   Queue* q = createQueue(); q->front = q->rear = -1; -> Option B

4. Quick Check:

   Proper queue pointer initialization = Queue* q = createQueue(); q->front = q->rear = -1; [OK]

Hint: Allocate memory before using pointer members [OK]

Common Mistakes:

• Using uninitialized pointers
• Assigning NULL to struct variable
• Not allocating memory before access

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], [6, 5, 4]]

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 has node 1, so output is [1].

2. Step 2: Traverse level 1 right to left

   Level 1 nodes are 2 and 3. Right to left means [3, 2].

3. Step 3: Traverse level 2 left to right

   Level 2 nodes are 4, 5, 6. Left to right means [4, 5, 6].

4. Final Answer:

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

5. Quick Check:

   Zigzag order matches [[1], [3, 2], [4, 5, 6]] [OK]

Hint: Alternate direction each level, start left to right [OK]

Common Mistakes:

• Not reversing order on alternate levels
• Mixing node values order
• Confusing left and right children

4. Consider this snippet for Zigzag Level Order Traversal in C:

while (!isEmpty(queue)) {
    int size = queueSize(queue);
    for (int i = 0; i < size; i++) {
        Node* node = dequeue(queue);
        if (leftToRight) {
            addToResult(node->val);
        } else {
            addToResultAtFront(node->val);
        }
        if (node->left) enqueue(queue, node->left);
        if (node->right) enqueue(queue, node->right);
    }
    leftToRight = !leftToRight;
}

What is the main bug in this code?

medium

A. The for loop should run until queue is empty, not fixed size.

B. leftToRight flag is not toggled correctly.

C. Using addToResultAtFront causes inefficient insertion, should use a stack.

D. Nodes are enqueued after processing, should enqueue before.

Solution

1. Step 1: Analyze insertion method for zigzag

   Adding elements at front of a list repeatedly is inefficient; a stack or deque is better for reversing order.

2. Step 2: Check other parts

   leftToRight toggling is correct. Enqueuing children after processing is standard. For loop running fixed size is correct to process current level only.

3. Final Answer:

   Using addToResultAtFront causes inefficient insertion, should use a stack. -> Option C

4. Quick Check:

   Efficient reversal needs stack/deque, not front insertion [OK]

Hint: Use stack or deque for reverse order insertion [OK]

Common Mistakes:

• Not toggling direction flag
• Enqueuing nodes before processing
• Incorrect loop bounds for level size

5. You want to perform Zigzag Level Order Traversal on a binary tree but only print nodes at odd levels (1, 3, 5, ...). Which modification is correct?

hard

A. Add a level counter and print results only when level % 2 == 1.

B. Skip enqueuing nodes at even levels.

C. Toggle leftToRight only on odd levels.

D. Reverse the entire traversal output after completion.

Solution

1. Step 1: Track current level number

   Maintain a counter for levels starting at 1 for root level.

2. Step 2: Print only odd levels

   When processing each level, print or store nodes only if level number is odd (level % 2 == 1).

3. Step 3: Keep traversal logic unchanged

   Enqueue all children normally and toggle direction each level to maintain zigzag pattern.

4. Final Answer:

   Add a level counter and print results only when level % 2 == 1. -> Option A

5. Quick Check:

   Filter output by odd levels using counter [OK]

Hint: Use level counter and print only odd levels [OK]

Common Mistakes:

• Skipping enqueuing nodes breaks traversal
• Toggling direction only on odd levels breaks zigzag
• Reversing output after traversal is incorrect