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

↓

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

Start from root, process nodes level by level using a queue, alternate the order of values collected each level to create zigzag pattern.

Execution Sample

DSA Python

def zigzagLevelOrder(root):
    if not root:
        return []
    result, queue, level = [], [root], 0
    while queue:
        level_vals = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            level_vals.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        if level % 2 == 1:
            level_vals.reverse()
        result.append(level_vals)
        level += 1
    return result

This code collects nodes level by level, reversing the order of values on odd levels to create zigzag traversal.

Execution Table

Step	Operation	Nodes in Queue	Level	Level Values Collected	Queue After Adding Children	Visual State
1	Initialize with root node 1	[1]	0	[]	[1]	Level 0: []
2	Process node 1	[]	0	[1]	[2, 3]	Level 0: [1]
3	Add level values (left to right)	[2, 3]	0	[1]	[2, 3]	Result: [[1]]
4	Process node 2	[3]	1	[2]	[3, 4, 5]	Level 1: [2]
5	Process node 3	[4, 5]	1	[2, 3]	[4, 5, 6, 7]	Level 1: [2, 3]
6	Add level values (right to left)	[4, 5, 6, 7]	1	[3, 2]	[4, 5, 6, 7]	Result: [[1], [3, 2]]
7	Process node 4	[5, 6, 7]	2	[4]	[5, 6, 7]	Level 2: [4]
8	Process node 5	[6, 7]	2	[4, 5]	[6, 7]	Level 2: [4, 5]
9	Process node 6	[7]	2	[4, 5, 6]	[7]	Level 2: [4, 5, 6]
10	Process node 7	[]	2	[4, 5, 6, 7]	[]	Level 2: [4, 5, 6, 7]
11	Add level values (left to right)	[]	2	[4, 5, 6, 7]	[]	Result: [[1], [3, 2], [4, 5, 6, 7]]
12	Queue empty, end traversal	[]	3	[]	[]	Traversal complete

💡 Queue is empty, all levels processed

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 11	Final
queue	[1]	[2, 3]	[4, 5, 6, 7]	[]	[]
level	0	1	2	3	3
level_vals	[]	[]	[]	[]	[]
result	[]	[[1]]	[[1], [3, 2]]	[[1], [3, 2], [4, 5, 6, 7]]	[[1], [3, 2], [4, 5, 6, 7]]

Key Moments - 3 Insights

Why do we reverse the level values only on odd levels?

Because zigzag means alternating order: even levels go left to right, odd levels right to left. See execution_table rows 3 and 6 where reversal happens only at level 1.

Why do we use a queue to hold nodes for the next level?

The queue keeps track of nodes to process in order. After processing current level nodes, their children are added to the queue for the next level. This is shown in execution_table rows 2, 4, 5, 7-10.

What happens if the root is None?

The function returns an empty list immediately (see code line 2). No traversal happens because there is no tree.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the order of level values collected?

A [3, 2]

B [2, 3]

C [1]

D [4, 5, 6, 7]

💡 Hint

Check the 'Level Values Collected' column at step 6 in execution_table

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

A Step 10

B Step 11

C Step 12

D Step 6

💡 Hint

Look for the row where 'Nodes in Queue' is empty and operation says traversal ends

If we did not reverse level values on odd levels, how would the result change at level 1?

A Level 1 values would be [2, 3]

B Level 1 values would be [3, 2]

C Level 1 values would be empty

D Level 1 values would be [1]

💡 Hint

Refer to execution_table step 6 and key_moments about reversal

Concept Snapshot

Zigzag Level Order Traversal:
- Use a queue to process nodes level by level
- Collect node values each level
- Reverse values on odd levels for zigzag pattern
- Add children to queue for next 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 hold nodes of the current level. For each level, we collect node values in order. On even levels, we keep left to right order. On odd levels, we reverse the order to create a zigzag pattern. After processing a level, we add all children of nodes to the queue for the next level. We repeat until the queue is empty, meaning all nodes are processed. The final result is a list of lists, each inner list representing a level's node values in zigzag order.

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 traverses the tree using depth-first search.

B. It visits nodes only at even levels.

C. It visits nodes in reverse order of their values.

D. It alternates the direction of traversal at each level, left to right then right to left.

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 each level: first left to right, then right to left, and so on.

3. Final Answer:

   It alternates the direction of traversal at each level, left to right then right to left. -> Option D

4. Quick Check:

   Zigzag = alternate directions [OK]

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

Common Mistakes:

• Thinking it only visits even levels
• Confusing with reverse value order
• Mixing with depth-first search

2. Which of the following Python code snippets correctly initializes a queue for level order traversal in zigzag pattern?

easy

A. from collections import deque
queue = deque([root])

B. queue = list(root)

C. queue = set(root)

D. queue = root.pop()

Solution

1. Step 1: Identify correct queue initialization

   For level order traversal, a queue is needed; deque from collections is ideal.

2. Step 2: Check each option

   from collections import deque queue = deque([root]) uses deque with root node inside, correct for BFS. Others misuse list, set, or pop method.

3. Final Answer:

   from collections import deque\nqueue = deque([root]) -> Option A

4. Quick Check:

   Use deque for queue in BFS [OK]

Hint: Use deque with root inside for BFS queue [OK]

Common Mistakes:

• Using list instead of deque for queue
• Using set which is unordered
• Calling pop on root which is a node, not a list

3. What is the output of the zigzag level order traversal for the binary tree below?

    1
   / \
  2   3
 / \   \
4   5   6

Assuming the traversal starts left to right at level 0.

medium

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

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

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

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

Solution

1. Step 1: Traverse level 0 left to right

   Level 0 has node 1, so output is [1].

2. Step 2: Traverse level 1 right to left

   Level 1 nodes are 2 and 3; reversed order is [3, 2].

3. Step 3: Traverse level 2 left to right

   Level 2 nodes are 4, 5, 6; order is [4, 5, 6].

4. Final Answer:

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

5. Quick Check:

   Zigzag levels alternate direction [OK]

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

Common Mistakes:

• Not reversing the order on odd levels
• Reversing the wrong levels
• Mixing node values order

4. The following code attempts zigzag level order traversal but produces incorrect output. What is the main error?

def zigzag(root):
    if not root:
        return []
    from collections import deque
    queue = deque([root])
    result = []
    left_to_right = True
    while queue:
        level_size = len(queue)
        level_nodes = []
        for _ in range(level_size):
            node = queue.popleft()
            if left_to_right:
                level_nodes.append(node.val)
            else:
                level_nodes.insert(0, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_nodes)
        # Missing toggle of direction here
    return result

medium

A. The direction flag 'left_to_right' is never toggled inside the loop.

B. The queue is not initialized correctly.

C. Nodes are appended to the wrong end of the queue.

D. The function does not check if root is null.

Solution

1. Step 1: Analyze direction toggle usage

   The variable 'left_to_right' controls order but is never changed inside the loop.

2. Step 2: Understand effect of missing toggle

   Without toggling, traversal direction stays same every level, so no zigzag effect.

3. Final Answer:

   The direction flag 'left_to_right' is never toggled inside the loop. -> Option A

4. Quick Check:

   Toggle direction each level [OK]

Hint: Toggle direction flag after each level [OK]

Common Mistakes:

• Forgetting to toggle direction
• Incorrect queue initialization
• Misusing queue append/popleft

5. Given a binary tree, how would you modify the zigzag level order traversal to return the sum of node values at each level instead of the nodes themselves?

hard

A. Reverse the entire result list at the end.

B. Accumulate the sum of values in 'level_nodes' before appending to result.

C. Use a stack instead of a queue to store nodes.

D. Append node values directly to result without using 'level_nodes'.

Solution

1. Step 1: Understand current storage of nodes per level

   Currently, nodes are collected in 'level_nodes' list for each level.

2. Step 2: Modify to sum values

   Instead of appending the list, calculate sum(level_nodes) and append that sum to result.

3. Final Answer:

   Accumulate the sum of values in 'level_nodes' before appending to result. -> Option B

4. Quick Check:

   Sum level nodes before appending [OK]

Hint: Sum values in level list before adding to result [OK]

Common Mistakes:

• Appending nodes instead of sums
• Using stack instead of queue incorrectly
• Reversing result instead of levels