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.

Practice

1. What does Zigzag Level Order Traversal of a binary tree mean?

easy

A. Traverse nodes level by level, alternating left to right and right to left

B. Traverse nodes only from left to right at each level

C. Traverse nodes only from right to left at each level

D. Traverse nodes randomly without any order

Solution

1. Step 1: Understand level order traversal

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

2. Step 2: Add zigzag pattern

   Zigzag means alternate direction each level: first left to right, then right to left, and so on.

3. Final Answer:

   Traverse nodes level by level, alternating left to right and right to left -> Option A

4. Quick Check:

   Zigzag = alternate directions [OK]

Hint: Remember zigzag means alternate directions each level [OK]

Common Mistakes:

• Thinking traversal is always left to right
• Confusing zigzag with preorder or inorder traversal
• Ignoring the alternating direction pattern

2. Which of the following C++ code snippets correctly initializes a queue for level order traversal?

easy

A. std::list q; q.push_front(root);

B. std::stack q; q.push(root);

C. std::vector q; q.push_back(root);

D. std::queue q; q.push(root);

Solution

1. Step 1: Identify correct data structure for level order

   Level order traversal uses a queue to process nodes FIFO (first in, first out).

2. Step 2: Check code snippets

   std::queue q; q.push(root); uses std::queue and pushes root correctly. Others use stack, vector, or list incorrectly for this purpose.

3. Final Answer:

   std::queue q; q.push(root); -> Option D

4. Quick Check:

   Queue for level order = std::queue q; q.push(root); [OK]

Hint: Use queue for level order traversal, not stack or vector [OK]

Common Mistakes:

• Using stack instead of queue
• Using vector push_back but no FIFO behavior
• Using list with push_front which reverses order

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], [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. Zigzag means reverse order here: [3, 2].

3. Step 3: Traverse level 2 left to right

   Level 2 nodes are 4, 5, 6 from left to right: [4, 5, 6].

4. Final Answer:

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

5. Quick Check:

   Zigzag levels alternate direction [OK]

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

Common Mistakes:

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

4. Identify the bug in this C++ snippet for zigzag traversal:

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

medium

A. Using vector<int> level(size) instead of vector<int> level

B. Incorrect queue initialization

C. Missing toggle of leftToRight after each level

D. Not checking if root is null

Solution

1. Step 1: Analyze loop for toggling direction

   The variable leftToRight controls direction but is never changed inside the loop.

2. Step 2: Identify missing toggle

   Without toggling leftToRight = !leftToRight; after processing each level, zigzag pattern won't alternate.

3. Final Answer:

   Missing toggle of leftToRight after each level -> Option C

4. Quick Check:

   Toggle direction each level [OK]

Hint: Toggle direction flag after each level to alternate traversal [OK]

Common Mistakes:

• Forgetting to flip leftToRight boolean
• Incorrect indexing in level vector
• Not pushing child nodes properly

5. Given a binary tree, how would you modify the zigzag level order traversal to return a flat vector of node values instead of a vector of vectors? For example, for tree:

    1
   / \
  2   3
 /     \
4       5

The output should be: [1, 3, 2, 4, 5]

hard

A. Use a stack instead of queue to store nodes for zigzag traversal

B. Perform normal zigzag traversal, then flatten the result vectors into one vector

C. Traverse all nodes left to right ignoring zigzag pattern

D. Return only the last level nodes in zigzag order

Solution

1. Step 1: Perform standard zigzag traversal

   Use queue and toggle direction each level to get vector of vectors with zigzag order.

2. Step 2: Flatten the vector of vectors

   Combine all inner vectors into a single vector preserving order to get flat list.

3. Final Answer:

   Perform normal zigzag traversal, then flatten the result vectors into one vector -> Option B

4. Quick Check:

   Flatten zigzag levels to one vector [OK]

Hint: Flatten after zigzag traversal to get single list [OK]

Common Mistakes:

• Trying to zigzag directly into flat vector without levels
• Using stack incorrectly for zigzag
• Ignoring zigzag pattern and traversing left to right only