Zigzag Level Order Traversal in DSA Go

Mental Model

We visit nodes level by level but alternate the direction of visiting nodes at each level.

Analogy: Imagine reading lines of text where you read the first line left to right, the next line right to left, then left to right again, zigzagging as you go down.

      1
     / \
    2   3
   / \   \
  4   5   6

Level 0: 1 (left to right)
Level 1: 3 -> 2 (right to left)
Level 2: 4 -> 5 -> 6 (left to right)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3 -> 4, 5, null, 6 (as shown in ascii_picture)

Goal: Traverse the tree level by level, alternating direction each level, collecting node values in that order

Step 1: Start at root level (level 0), traverse left to right

Level 0: [1]
Result: [[1]]

Why: We begin traversal from the root, left to right as first level

Step 2: Move to level 1, traverse right to left

Level 1 nodes: 2 -> 3
Traverse right to left: [3, 2]
Result: [[1], [3, 2]]

Why: Alternate direction to right to left for level 1

Step 3: Move to level 2, traverse left to right

Level 2 nodes: 4, 5, 6
Traverse left to right: [4, 5, 6]
Result: [[1], [3, 2], [4, 5, 6]]

Why: Alternate direction back to left to right for level 2

Result:

Final zigzag traversal: [[1], [3, 2], [4, 5, 6]]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	result := [][]int{}
	queue := []*TreeNode{root}
	leftToRight := true

	for len(queue) > 0 {
		size := len(queue)
		level := make([]int, size)

		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]

			// Decide position based on direction
			index := i
			if !leftToRight {
				index = size - 1 - i
			}
			level[index] = node.Val

			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		result = append(result, level)
		leftToRight = !leftToRight // alternate direction
	}

	return result
}

func main() {
	// Construct the tree:
	//      1
	//     / \
	//    2   3
	//   / \   \
	//  4   5   6

	n4 := &TreeNode{Val: 4}
	n5 := &TreeNode{Val: 5}
	n6 := &TreeNode{Val: 6}
	n2 := &TreeNode{Val: 2, Left: n4, Right: n5}
	n3 := &TreeNode{Val: 3, Right: n6}
	n1 := &TreeNode{Val: 1, Left: n2, Right: n3}

	result := zigzagLevelOrder(n1)
	fmt.Println(result)
}

if root == nil { return [][]int{} }

handle empty tree edge case

for len(queue) > 0 {

process nodes level by level until no nodes left

size := len(queue)

number of nodes at current level

for i := 0; i < size; i++ {

iterate over all nodes in current level

node := queue[0]; queue = queue[1:]

dequeue node to process

index := i; if !leftToRight { index = size - 1 - i }

determine position in level slice based on direction

level[index] = node.Val

place node value in correct position for zigzag

if node.Left != nil { queue = append(queue, node.Left) }

enqueue left child if exists

if node.Right != nil { queue = append(queue, node.Right) }

enqueue right child if exists

result = append(result, level)

add current level's values to result

leftToRight = !leftToRight

flip direction for next level

Output

[[1] [3 2] [4 5 6]]

Complexity Analysis

Time: O(n) because each node is visited exactly once during the traversal

Space: O(n) because we store nodes in a queue and the result list proportional to the number of nodes

vs Alternative: Compared to normal level order traversal, zigzag adds a small overhead to reverse order but still runs in linear time

Edge Cases

empty tree

returns empty list immediately

DSA Go

if root == nil { return [][]int{} }

single node tree

returns list with one level containing the single node

DSA Go

for len(queue) > 0 { ... } handles this naturally

tree with only left or only right children

traverses levels correctly alternating direction even if some children are missing

DSA Go

if node.Left != nil { ... } and if node.Right != nil { ... }

When to Use This Pattern

When a problem asks for level order traversal but with alternating directions each level, use the zigzag level order traversal pattern to handle direction switching efficiently.

Common Mistakes

Mistake: Not alternating the direction correctly causing all levels to be left to right or right to left
Fix: Use a boolean flag that flips after each level to control the direction of insertion

Mistake: Appending nodes in wrong order causing incorrect zigzag output
Fix: Calculate the index in the level slice based on direction instead of reversing the entire list after traversal

Summary

Traverses a binary tree level by level, alternating the order of nodes at each level.

Use when you need to visit nodes in a zigzag pattern instead of straight left-to-right level order.

The key is to switch direction each level and place nodes accordingly while traversing.

Practice

1. What does the Zigzag Level Order Traversal of a binary tree do differently compared to a normal level order traversal?

easy

A. It alternates the direction of traversal at each level, switching between left-to-right and right-to-left.

B. It only traverses the left subtree of the tree.

C. It visits nodes in a random order at each level.

D. It traverses nodes only in right-to-left order for all levels.

Solution

1. Step 1: Understand normal level order traversal

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

2. Step 2: Identify zigzag difference

   Zigzag traversal changes direction every level: first left-to-right, then right-to-left, and so on.

3. Final Answer:

   It alternates the direction of traversal at each level, switching between left-to-right and right-to-left. -> Option A

4. Quick Check:

   Zigzag = alternate directions [OK]

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

Common Mistakes:

• Thinking traversal is always left-to-right
• Confusing zigzag with random order
• Ignoring direction change at each level

2. Which of the following Go code snippets correctly initializes a queue for level order traversal in Zigzag Level Order Traversal?

easy

A. queue := make([]int, 0)

B. queue := []int{root}

C. queue := map[int]*TreeNode{}

D. queue := []*TreeNode{root}

Solution

1. Step 1: Identify the queue type needed

   Queue should hold pointers to TreeNode structs, so []*TreeNode is correct.

2. Step 2: Check each option's correctness

   queue := []*TreeNode{root} uses []*TreeNode with root node, correct for traversal. Options A and B use int slices, wrong type. queue := map[int]*TreeNode{} uses map, not queue.

3. Final Answer:

   queue := []*TreeNode{root} -> Option D

4. Quick Check:

   Queue holds TreeNode pointers = queue := []*TreeNode{root} [OK]

Hint: Queue must hold TreeNode pointers, not ints or maps [OK]

Common Mistakes:

• Using int slices instead of TreeNode pointers
• Using map instead of slice for queue
• Not initializing queue with root node

3. Given the binary tree:

    1
   / \
  2   3
 / \   \
4   5   6

What is the output of Zigzag Level Order Traversal?

medium

A. [[1], [2, 3], [4, 5, 6]]

B. [[1], [2, 3], [6, 5, 4]]

C. [[1], [3, 2], [4, 5, 6]]

D. [[1], [3, 2], [6, 5, 4]]

Solution

1. Step 1: Traverse level 0 and 1 with direction

   Level 0: left-to-right -> [1]. Level 1: right-to-left -> [3, 2].

2. Step 2: Traverse level 2 left-to-right

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

3. Final Answer:

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

4. Quick Check:

   Zigzag levels alternate directions = [[1], [3, 2], [4, 5, 6]] [OK]

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

Common Mistakes:

• Not reversing nodes on odd levels
• Reversing nodes on even levels incorrectly
• Mixing node order at last level

4. Consider this Go code snippet for Zigzag Level Order Traversal:

for len(queue) > 0 {
    levelSize := len(queue)
    var level []int
    for i := 0; i < levelSize; i++ {
        node := queue[0]
        queue = queue[1:]
        level = append(level, node.Val)
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    if leftToRight {
        result = append(result, level)
    } else {
        reverse(level)
        result = append(result, level)
    }
    leftToRight = !leftToRight
}

What is the main bug in this code?

medium

A. The reverse function is called but not defined or implemented.

B. The queue is not updated correctly after popping the first element.

C. The variable leftToRight is never initialized before use.

D. The level slice is appended before processing child nodes.

Solution

1. Step 1: Check queue update correctness

   Queue is updated by slicing off first element correctly, no bug here.

2. Step 2: Verify reverse function usage

   reverse(level) is called but no definition or implementation is shown, causing compile error.

3. Final Answer:

   The reverse function is called but not defined or implemented. -> Option A

4. Quick Check:

   Undefined reverse function causes error [OK]

Hint: Ensure all helper functions like reverse are implemented [OK]

Common Mistakes:

• Assuming reverse is built-in in Go
• Ignoring initialization of leftToRight (usually done before loop)
• Misunderstanding queue slicing syntax

5. You want to implement Zigzag Level Order Traversal but optimize space by avoiding reversing slices. Which approach is best?

hard

A. Use a queue and reverse the slice after each level as usual.

B. Use two stacks to alternate pushing nodes in correct order per level.

C. Use recursion with a global list and reverse at the end.

D. Traverse all nodes left-to-right and then reverse the entire result.

Solution

1. Step 1: Understand reversing cost

   Reversing slices after each level adds extra time and space overhead.

2. Step 2: Use two stacks for order control

   Two stacks let you push child nodes in order that naturally produces zigzag traversal without reversing.

3. Final Answer:

   Use two stacks to alternate pushing nodes in correct order per level. -> Option B

4. Quick Check:

   Two stacks avoid reversing slices [OK]

Hint: Two stacks method avoids reversing slices [OK]

Common Mistakes:

• Relying on reversing slices every level
• Using recursion without order control
• Reversing entire result instead of per level