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

↓

Reverse order for odd levels

↓

Add children to queue

↓

Move to next level

↓

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 Go

func zigzagLevelOrder(root *TreeNode) [][]int {
 if root == nil { return [][]int{} }
 queue := []*TreeNode{root}
 result := [][]int{}
 level := 0
 for len(queue) > 0 {
  levelSize := len(queue)
  levelNodes := make([]int, levelSize)
  for i := 0; i < levelSize; i++ {
   node := queue[0]
   queue = queue[1:]
   if level%2 == 0 {
    levelNodes[i] = node.Val
   } else {
    levelNodes[levelSize-1-i] = node.Val
   }
   if node.Left != nil {
    queue = append(queue, node.Left)
   }
   if node.Right != nil {
    queue = append(queue, node.Right)
   }
  }
  result = append(result, levelNodes)
  level++
 }
 return result
}

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

Execution Table

Step	Operation	Nodes in Queue	Level	Order	Values Collected	Queue After Adding Children	Visual State
1	Start with root node	[3]	0	Left to Right	[3]	[9, 20]	Level 0: 3
2	Process level 1 nodes	[9, 20]	1	Right to Left	[20, 9]	[15, 7]	Level 1: 20 -> 9
3	Process level 2 nodes	[15, 7]	2	Left to Right	[15, 7]	[]	Level 2: 15 -> 7
4	Queue empty, traversal ends	[]	-	-	-	-	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
result	[]	[[3]]	[[3],[20,9]]	[[3],[20,9],[15,7]]	[[3],[20,9],[15,7]]

Key Moments - 3 Insights

Why do we reverse the order of values at odd levels?

At odd levels, we collect node values right to left to create the zigzag pattern. See execution_table row 2 where level 1 order is 'Right to Left' and values are reversed.

How do we know when to stop the traversal?

We stop when the queue is empty, meaning no more nodes to process. This is shown in execution_table row 4 where the queue is empty and traversal ends.

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

Adding children after processing ensures we process nodes level by level. The queue after adding children in each step shows the next level nodes to process.

Visual Quiz - 3 Questions

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

A [9, 20]

B [15, 7]

C []

D [3]

💡 Hint

Check the 'Queue After Adding Children' column in row 1 of execution_table.

At which level do we collect values in right to left order?

A Level 0

B Level 1

C Level 2

D Traversal end

💡 Hint

Look at the 'Order' column in execution_table rows.

If the root had no children, what would be the final result?

A [[3]]

B []

C [[3], []]

D [[]]

💡 Hint

Refer to variable_tracker 'result' after step 1 and the queue state.

Concept Snapshot

Zigzag Level Order Traversal:
- Traverse tree level by level using a queue.
- Alternate order of node values each level (left-right, then right-left).
- Collect values per level, reverse on odd levels.
- Add children to queue after processing current level.
- Stop when queue is empty.
- Return list of levels with zigzag order.

Full Transcript

Zigzag Level Order Traversal visits nodes level by level in a binary tree. We start at the root and use a queue to keep track of nodes at each level. For each level, we collect node values. On even levels, we collect left to right. On odd levels, we reverse the order to right to left. After processing a level, we add all children of nodes in that level to the queue for the next level. We repeat until the queue is empty, meaning all nodes are processed. The result is a list of lists, each inner list representing a level's node values in zigzag order.