Zigzag Level Order Traversal in DSA Javascript - 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 current level 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 for each level.

Execution Sample

DSA Javascript

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let level = 0;
  while (queue.length) {
    const size = queue.length;
    const currentLevel = [];
    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 in zigzag level order, alternating the direction of node values at each level.

Execution Table

Step	Operation	Nodes in Queue	Current Level Nodes	Level Number	Order	Current Level Values	Queue After Processing	Visual State
1	Start with root node	[3]	[3]	0	Left to Right	[3]	[9, 20]	Level 0: 3
2	Process level 1 nodes	[9, 20]	[9, 20]	1	Right to Left	[20, 9]	[15, 7]	Level 1: 20 -> 9
3	Process level 2 nodes	[15, 7]	[15, 7]	2	Left to Right	[15, 7]	[]	Level 2: 15 -> 7
4	Queue empty, end	[]	[]	3	-	[]	[]	Traversal complete

💡 Queue is empty, all levels processed

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
queue	[3]	[9, 20]	[15, 7]	[]	[]
level	0	1	2	3	3
currentLevel	[]	[3]	[20, 9]	[15, 7]	[]
result	[]	[[3]]	[[3], [20, 9]]	[[3], [20, 9], [15, 7]]	[[3], [20, 9], [15, 7]]

Key Moments - 3 Insights

Why do we use unshift for odd levels instead of push?

At odd levels (see Step 2 in execution_table), we add node values at the front to reverse the order, creating the zigzag effect. Using push would keep left-to-right order.

Why do we process all nodes in the queue at once for each level?

Processing all nodes currently in the queue (Step 2 and 3) ensures we handle one level fully before moving to the next, preserving level order traversal.

What happens if the tree is empty?

The code returns an empty list immediately (not shown in table), so no processing occurs.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the order of node values collected?

A Left to Right

B Right to Left

C Random

D No order

💡 Hint

Check the 'Order' column at Step 2 in execution_table

At which step does the queue become empty?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Nodes in Queue' column in execution_table

If we change the code to always use push instead of unshift, how would the currentLevel array at Step 2 change?

A [9, 20]

B [20, 9]

C [3]

D []

💡 Hint

Refer to the 'Current Level Values' column at Step 2 and how unshift vs push affects order

Concept Snapshot

Zigzag Level Order Traversal:
- Traverse tree level by level using a queue
- For even levels, add node values left to right
- For odd levels, add 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 level by level in a binary tree. It uses a queue to hold nodes of the current level. For each level, it collects node values in left-to-right order if the level number is even, and right-to-left order if odd. This is done by pushing or unshifting values into a temporary array. After processing all nodes of a level, their children are added to the queue for the next level. This repeats until no nodes remain. The result is a list of lists showing node values in zigzag order.