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

Traverse the tree level by level, alternating the order of node values between left-to-right and right-to-left at each level.

Execution Sample

DSA C++

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
  vector<vector<int>> result;
  if (!root) return result;
  queue<TreeNode*> q; q.push(root);
  bool leftToRight = true;
  while (!q.empty()) {
    int size = q.size();
    vector<int> level(size);
    for (int i = 0; i < size; ++i) {
      TreeNode* node = q.front(); q.pop();
      int index = leftToRight ? i : (size - 1 - i);
      level[index] = node->val;
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    result.push_back(level);
    leftToRight = !leftToRight;
  }
  return result;
}

This code traverses a binary tree in zigzag level order, alternating the direction of node values at each level.

Execution Table

Step	Operation	Queue State (Nodes)	Level Size	Index i	Index for Insert	Level Values	Direction	Visual State
1	Initialize queue with root (1)	[1]	N/A	N/A	N/A	[]	Left to Right	Level 0: []
2	Start level 0 processing	[1]	1	0	0	[1]	Left to Right	Level 0: [1]
3	Add children of 1 (2,3)	[2,3]	N/A	N/A	N/A	[1]	Left to Right	Level 0 done: [1]
4	Start level 1 processing	[2,3]	2	0	1	[0,0]	Right to Left	Level 1: [0,0]
5	Process node 2	[3]	2	0	1	[0,2]	Right to Left	Level 1: [0,2]
6	Add children of 2 (4,5)	[3,4,5]	N/A	N/A	N/A	[0,2]	Right to Left	Level 1 partial: [0,2]
7	Process node 3	[4,5]	2	1	0	[3,2]	Right to Left	Level 1: [3,2]
8	Add children of 3 (6,7)	[4,5,6,7]	N/A	N/A	N/A	[3,2]	Right to Left	Level 1 done: [3,2]
9	Start level 2 processing	[4,5,6,7]	4	0	0	[0,0,0,0]	Left to Right	Level 2: [0,0,0,0]
10	Process node 4	[5,6,7]	4	0	0	[4,0,0,0]	Left to Right	Level 2: [4,0,0,0]
11	Process node 5	[6,7]	4	1	1	[4,5,0,0]	Left to Right	Level 2: [4,5,0,0]
12	Process node 6	[7]	4	2	2	[4,5,6,0]	Left to Right	Level 2: [4,5,6,0]
13	Process node 7	[]	4	3	3	[4,5,6,7]	Left to Right	Level 2: [4,5,6,7]
14	No more nodes in queue	[]	N/A	N/A	N/A	[4,5,6,7]	N/A	Traversal complete

💡 Queue is empty, all levels processed

Variable Tracker

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

Key Moments - 3 Insights

Why do we use 'index = leftToRight ? i : (size - 1 - i)' to insert values?

This formula reverses the insertion order on odd levels to achieve zigzag order, as shown in execution_table rows 4-8 where right to left inserts at reversed indices.

Why do we push children into the queue in normal left-to-right order even on right-to-left levels?

Children are always added left then right to maintain correct traversal order for next level, as seen in steps 6 and 8, ensuring the queue has nodes in proper order for next level processing.

What stops the traversal loop?

The loop stops when the queue is empty, meaning no more nodes to process, as shown in step 14 where queue is empty and traversal ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the 'Level Values' array?

A [3,2]

B [2,3]

C [0,0]

D [1]

💡 Hint

Check the 'Level Values' column at step 7 in execution_table

At which step does the traversal switch direction from left to right to right to left?

A Step 9

B Step 2

C Step 4

D Step 14

💡 Hint

Look at the 'Direction' column in execution_table to find when it changes from Left to Right to Right to Left

If the root node had no children, what would be the queue state after step 3?

A [1]

B Empty queue []

C [null]

D [2,3]

💡 Hint

Refer to execution_table step 3 where children are added; no children means queue becomes empty

Concept Snapshot

Zigzag Level Order Traversal:
- Traverse tree level by level using a queue
- Alternate direction each level: left-to-right, then right-to-left
- Insert node values in vector accordingly
- Add children left to right always
- Stop when queue is empty
- Result is list of levels in zigzag order

Full Transcript

Zigzag Level Order Traversal visits nodes level by level in a binary tree. We use a queue to hold nodes of the current level. For each level, we collect node values in a vector. If the level is even, we insert values left to right. If odd, we insert right to left by reversing the index. Children are always added left then right to the queue for the next level. We repeat until the queue is empty. This produces a zigzag pattern of node values across levels.