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.