Zigzag Level Order Traversal in DSA Typescript - 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

↓

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

Start from the root, process nodes level by level using a queue, alternate the order of values collected at each level to create a zigzag pattern.

Execution Sample

DSA Typescript

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let level = 0;
  while (queue.length) {
    const size = queue.length;
    const currentLevel: number[] = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      if (level % 2 === 0) currentLevel.push(node.val);
      else currentLevel.unshift(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(currentLevel);
    level++;
  }
  return result;
}

This code traverses a binary tree level by level, collecting node values in zigzag order by alternating insertion direction each level.

Execution Table

Step	Operation	Nodes in Queue	Level	Current Level Nodes Processed	Current Level Values	Queue After Processing	Visual State
1	Initialize queue with root (1)	[1]	0	0/1	[]	[1]	Level 0: []
2	Process node 1	[]	0	1/1	[1]	[2,3]	Level 0: [1]
3	Add current level values to result	[2,3]	0	1/1	[1]	[2,3]	Result: [[1]]
4	Increase level to 1	[2,3]	1	0/2	[]	[2,3]	Level 1: []
5	Process node 2	[3]	1	1/2	[2]	[3,4,5]	Level 1: [2] (insert at front)
6	Process node 3	[4,5]	1	2/2	[3,2]	[4,5,6,7]	Level 1: [3,2] (insert at front)
7	Add current level values to result	[4,5,6,7]	1	2/2	[3,2]	[4,5,6,7]	Result: [[1],[3,2]]
8	Increase level to 2	[4,5,6,7]	2	0/4	[]	[4,5,6,7]	Level 2: []
9	Process node 4	[5,6,7]	2	1/4	[4]	[5,6,7]	Level 2: [4]
10	Process node 5	[6,7]	2	2/4	[4,5]	[6,7]	Level 2: [4,5]
11	Process node 6	[7]	2	3/4	[4,5,6]	[7]	Level 2: [4,5,6]
12	Process node 7	[]	2	4/4	[4,5,6,7]	[]	Level 2: [4,5,6,7]
13	Add current level values to result	[]	2	4/4	[4,5,6,7]	[]	Result: [[1],[3,2],[4,5,6,7]]
14	Queue empty, end traversal	[]	3	0/0	[]	[]	Traversal complete

💡 Queue is empty, all levels processed

Variable Tracker

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

Key Moments - 3 Insights

Why do we use unshift (insert at front) on odd levels instead of push?

Because on odd levels we want to reverse the order of node values to create the zigzag pattern. This is shown in execution_table rows 5 and 6 where values are inserted at the front, reversing their order.

Why do we process all nodes currently in the queue before increasing the level?

Because each level consists of all nodes currently in the queue at the start of the loop iteration. This ensures we collect values level by level, as seen in execution_table rows 2-3 and 5-7.

What happens if the tree is empty (root is null)?

The function returns an empty array immediately, as shown in the code sample line 2: if (!root) return []. No traversal happens.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the order of current level values?

A [2, 3]

B [1]

C [3, 2]

D [4, 5, 6, 7]

💡 Hint

Check the 'Current Level Values' column at step 6 in execution_table

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

A Step 12

B Step 14

C Step 13

D Step 10

💡 Hint

Look for the step where 'Queue' column is empty and 'Traversal complete' in Visual State

If we changed the code to always push node values (no unshift), how would the result change?

A All levels would be left to right order

B All levels would be right to left order

C The traversal would stop early

D The queue would never empty

💡 Hint

Refer to key_moments about why unshift is used on odd levels

Concept Snapshot

Zigzag Level Order Traversal:
- Use a queue to traverse tree level by level
- For even levels, append node values left to right
- For odd levels, insert node values right to left (using unshift)
- Add children to queue for next level
- Repeat until queue empty
- Return list of levels with zigzag order

Full Transcript

Zigzag Level Order Traversal visits nodes of a binary tree level by level, but alternates the order of values collected at each level to create a zigzag pattern. We start with the root node in a queue. While the queue is not empty, we process all nodes currently in the queue as one level. For even levels, we add node values to the current level list from left to right. For odd levels, we insert node values at the front to reverse the order. After processing a level, we add all children of nodes to the queue for the next level. We repeat this until the queue is empty. The final result is a list of lists, each representing a level's node values in zigzag order.

Practice

1. What is the main idea behind Zigzag Level Order Traversal of a binary tree?

easy

A. Traverse the tree only from right to left at all levels

B. Traverse the tree only from left to right at all levels

C. Traverse each level of the tree alternating between left-to-right and right-to-left order

D. Traverse nodes in random order without level consideration

Solution

1. Step 1: Understand level order traversal

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

2. Step 2: Identify zigzag pattern

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

3. Final Answer:

   Traverse each level of the tree alternating between left-to-right and right-to-left order -> Option C

4. Quick Check:

   Zigzag means alternating directions [OK]

Hint: Remember zigzag means switching direction each level [OK]

Common Mistakes:

• Thinking traversal is always left to right
• Confusing zigzag with normal level order
• Ignoring level-by-level traversal

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

easy

A. const queue = {}; queue.enqueue(root);

B. const queue = new Set<TreeNode>(); queue.add(root);

C. const queue: TreeNode[] = new TreeNode(); queue.push(root);

D. const queue: TreeNode[] = []; queue.push(root);

Solution

1. Step 1: Identify correct queue initialization

   In TypeScript, an array can be used as a queue with push and shift methods.

2. Step 2: Check each option

   const queue: TreeNode[] = []; queue.push(root); correctly declares an array and pushes root node. Others use wrong types or methods.

3. Final Answer:

   const queue: TreeNode[] = []; queue.push(root); -> Option D

4. Quick Check:

   Array with push is correct queue usage [OK]

Hint: Use array push/shift for queue in TypeScript [OK]

Common Mistakes:

• Using Set instead of queue
• Incorrect object initialization
• Using non-existent enqueue method

3. What is the output of the zigzag level order traversal for the binary tree below?

    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; reversed order is [3, 2].

3. Step 3: Traverse level 2 left to right

   Level 2 nodes are 4, 5, 6; order is [4, 5, 6].

4. Final Answer:

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

5. Quick Check:

   Zigzag alternates direction each level [OK]

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

Common Mistakes:

• Not reversing nodes on odd levels
• Mixing node order at last level
• Confusing left and right children order

4. Consider this TypeScript code snippet for zigzag traversal. What is the bug?

const result: number[][] = [];
const queue: TreeNode[] = [root];
let leftToRight = true;
while (queue.length > 0) {
  const levelSize = queue.length;
  const levelNodes: number[] = [];
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift()!;
    if (leftToRight) levelNodes.push(node.val);
    else levelNodes.unshift(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  result.push(levelNodes);
  // Missing toggle of leftToRight
}

medium

A. Children nodes are pushed in wrong order

B. leftToRight is never toggled, so traversal direction never changes

C. levelNodes.unshift() should be levelNodes.push() always

D. queue.shift() is used instead of queue.pop() causing wrong order

Solution

1. Step 1: Check direction toggle

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

2. Step 2: Understand effect of missing toggle

   Without toggling, direction stays same, so zigzag pattern breaks.

3. Final Answer:

   leftToRight is never toggled, so traversal direction never changes -> Option B

4. Quick Check:

   Toggle direction each level for zigzag [OK]

Hint: Toggle direction flag after each level [OK]

Common Mistakes:

• Forgetting to toggle leftToRight
• Using wrong queue methods
• Incorrectly adding nodes to level array

5. Given a binary tree, how would you modify the zigzag level order traversal to return a flat array of node values in zigzag order instead of nested arrays per level?

hard

A. Concatenate each level's nodes to a single array instead of pushing nested arrays

B. Use a stack instead of a queue for traversal

C. Traverse all nodes left to right ignoring zigzag

D. Return only the last level's nodes

Solution

1. Step 1: Understand current output format

   Zigzag traversal usually returns nested arrays, one per level.

2. Step 2: Modify to flat array

   Instead of pushing level arrays, append each level's nodes to a single result array.

3. Step 3: Keep zigzag order

   Maintain alternating direction logic while flattening output.

4. Final Answer:

   Concatenate each level's nodes to a single array instead of pushing nested arrays -> Option A

5. Quick Check:

   Flatten by concatenation, keep zigzag order [OK]

Hint: Append levels to one array instead of nested arrays [OK]

Common Mistakes:

• Changing traversal order incorrectly
• Using stack breaks level order
• Returning only partial nodes