Zigzag Level Order Traversal in DSA Java - Execution Trace

Concept Flow - Zigzag Level Order Traversal

Start at root node

↓

Initialize queue with root

↓

While queue not empty

↓

Process current level nodes

↓

Add children to queue

↓

Reverse order if zigzag level

↓

Add level to result

↓

Toggle zigzag direction

↓

Repeat until queue empty

↓

Return zigzag order list

Start from root, use a queue to process nodes level by level, reverse order on alternate levels to create zigzag pattern.

Execution Sample

DSA Java

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) level.add(node.val);
            else level.add(0, node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

Traverse tree level by level, add nodes left to right or right to left alternately to create zigzag order.

Execution Table

Step	Operation	Nodes in Queue	Level Nodes Collected	Visual State of Tree	Zigzag Direction
1	Start with root node 1	[1]	[]	1 / \ 2 3	Left to Right
2	Process level 1	[]	[1]	1 / \ 2 3	Left to Right
3	Add children 2,3 to queue	[2,3]	[1]	1 / \ 2 3	Left to Right
4	Toggle direction	[2,3]	[1]	1 / \ 2 3	Right to Left
5	Process level 2	[3]	[3,2]	1 / \ 2 3	Right to Left
6	Add children 4,5 from 2	[3,4,5]	[3,2]	1 / \ 2 3 / \ 4 5	Right to Left
7	Add child 6 from 3	[4,5,6]	[3,2]	1 / \ 2 3 / \ 4 5 6	Right to Left
8	Toggle direction	[4,5,6]	[3,2]	1 / \ 2 3 / \ 4 5 6	Left to Right
9	Process level 3	[]	[4,5,6]	1 / \ 2 3 / \ 4 5 6	Left to Right
10	No children to add	[]	[4,5,6]	1 / \ 2 3 / \ 4 5 6	Left to Right
11	Queue empty, end	[]	[4,5,6]	1 / \ 2 3 / \ 4 5 6	Left to Right

💡 Queue is empty, all levels processed

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	Final
queue	[1]	[2,3]	[4,5,6]	[]	[]
level	[]	[1]	[3,2]	[4,5,6]	[4,5,6]
result	[]	[[1]]	[[1],[3,2]]	[[1],[3,2],[4,5,6]]	[[1],[3,2],[4,5,6]]
leftToRight	true	false	true	false	false

Key Moments - 3 Insights

Why do we add nodes to the level list at the front when direction is right to left?

Because in the execution_table row 5, nodes 3 and 2 are added in reverse order by inserting at index 0, which reverses the level order to create the zigzag effect.

Why do we toggle the direction after processing each level?

As shown in rows 4 and 8, toggling leftToRight changes the insertion order for the next level, alternating between left-to-right and right-to-left traversal.

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

The code returns an empty result immediately, so no steps occur in the execution_table and the queue remains empty.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the order of nodes collected in the level list?

A [3, 2]

B [2, 3]

C [1]

D []

💡 Hint

Check the 'Level Nodes Collected' column at step 5 in the execution_table.

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

A Step 9

B Step 10

C Step 11

D Step 8

💡 Hint

Look at the 'Nodes in Queue' column in the execution_table to find when it becomes [].

If we did not toggle the zigzag direction, how would the 'Level Nodes Collected' change at step 5?

A [3, 2]

B [2, 3]

C [1]

D []

💡 Hint

Refer to the 'Zigzag Direction' column and how it affects insertion order in the execution_table.

Concept Snapshot

Zigzag Level Order Traversal:
- Use a queue to traverse tree level by level.
- Collect nodes in a list per level.
- Alternate insertion order each level (left-to-right, then right-to-left).
- Toggle direction after each level.
- Return list of levels showing zigzag pattern.

Full Transcript

Zigzag Level Order Traversal visits tree nodes level by level, but alternates the order of nodes collected each level. We start with the root node in a queue. For each level, we remove nodes from the queue, add their values to a list either left-to-right or right-to-left depending on the current direction, and add their children to the queue for the next level. After processing a level, we toggle the direction to reverse the order for the next level. This continues until the queue is empty, meaning all nodes have been visited. The result is a list of lists, each representing a level of the tree with nodes in zigzag order.

Practice

1. What is the main difference between a normal level order traversal and a zigzag level order traversal of a binary tree?

easy

A. Zigzag traversal alternates the direction of node visits at each level.

B. Zigzag traversal visits nodes only on odd levels.

C. Zigzag traversal visits nodes in reverse order at all levels.

D. Zigzag traversal visits nodes randomly without any order.

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: Understand zigzag traversal difference

   Zigzag traversal changes direction at each level, alternating between left-to-right and right-to-left.

3. Final Answer:

   Zigzag traversal alternates the direction of node visits at each level. -> Option A

4. Quick Check:

   Zigzag = alternate direction [OK]

Hint: Remember zigzag flips direction every level [OK]

Common Mistakes:

• Thinking zigzag visits only odd levels
• Assuming zigzag always goes right to left
• Confusing zigzag with random order

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

easy

A. Queue<TreeNode> queue = new ArrayList<>();

B. Queue<TreeNode> queue = new HashSet<>();

C. Queue<TreeNode> queue = new Stack<>();

D. Queue<TreeNode> queue = new LinkedList<>();

Solution

1. Step 1: Identify correct queue implementation

   Java's Queue interface is commonly implemented by LinkedList for FIFO behavior.

2. Step 2: Check other options

   ArrayList is a list, not a queue; Stack is LIFO, not queue; HashSet is a set, no order.

3. Final Answer:

   Queue<TreeNode> queue = new LinkedList<>(); -> Option D

4. Quick Check:

   Queue = LinkedList [OK]

Hint: Use LinkedList for queue in Java [OK]

Common Mistakes:

• Using ArrayList instead of Queue
• Using Stack which is LIFO, not FIFO
• Using HashSet which has no order

3. Given the binary tree below, what is the zigzag level order traversal output?

    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 nodes: [1]

2. Step 2: Traverse level 1 right to left

   Level 1 nodes: [2, 3] reversed to [3, 2]

3. Step 3: Traverse level 2 left to right

   Level 2 nodes: [4, 5, 6]

4. Final Answer:

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

5. Quick Check:

   Zigzag levels alternate direction [OK]

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

Common Mistakes:

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

4. Consider the following Java code snippet for zigzag traversal. What is the error?

Queue<TreeNode> queue = new LinkedList<>();
boolean leftToRight = true;
while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> level = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        if (leftToRight) level.add(node.val);
        else level.add(0, node.val);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    leftToRight = !leftToRight;
}

medium

A. The boolean flag leftToRight should not be toggled.

B. The queue should be a Stack for zigzag traversal.

C. The for loop condition should be i < size, not i <= size.

D. The level list should be a LinkedList instead of ArrayList.

Solution

1. Step 1: Analyze for loop condition

   The loop runs from i = 0 to i <= size, which means it runs size+1 times, causing poll() to return null once.

2. Step 2: Correct loop condition

   The loop should run exactly size times, so condition must be i < size.

3. Final Answer:

   The for loop condition should be i < size, not i <= size. -> Option C

4. Quick Check:

   Loop runs size times [OK]

Hint: Use i < size for loops over queue size [OK]

Common Mistakes:

• Using i <= size causing extra iteration
• Using Stack instead of Queue
• Not toggling direction flag

5. You want to implement zigzag level order traversal but optimize space by using a single deque (double-ended queue). Which approach correctly uses the deque to achieve zigzag traversal?

hard

A. Use deque to add nodes at front for left-to-right levels and remove from end; add nodes at end for right-to-left levels and remove from front.

B. Use deque to add nodes at the end for left-to-right levels and remove from front; add nodes at front for right-to-left levels and remove from end.

C. Use deque to add nodes only at end and remove from front for all levels.

D. Use deque to add nodes only at front and remove from end for all levels.

Solution

1. Step 1: Understand deque usage for zigzag

   For left-to-right levels, add children at the end and remove nodes from front to process in order.

2. Step 2: Reverse direction for right-to-left levels

   For right-to-left levels, add children at front and remove nodes from end to process in reverse order.

3. Final Answer:

   Use deque to add nodes at the end for left-to-right levels and remove from front; add nodes at front for right-to-left levels and remove from end. -> Option B

4. Quick Check:

   Deque add/remove ends alternate by level [OK]

Hint: Alternate deque ends for add/remove by level [OK]

Common Mistakes:

• Adding/removing from same end always
• Not reversing add/remove ends per level
• Using only queue or stack instead of deque