Zigzag Level Order Traversal in DSA Python

Mental Model

We visit tree nodes level by level, but switch direction each level, going left to right then right to left alternately.

Analogy: Imagine walking through floors of a building: on one floor you walk left to right, on the next floor you walk right to left, zigzagging as you go up.

      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 (see ascii picture)

Goal: Print nodes level by level, alternating direction each level

Step 1: Start at root level 0, direction left to right

Level 0: [1]

Why: We begin traversal from the root node going left to right

Step 2: Collect children of level 0 nodes for level 1

Level 1 nodes: 2 -> 3

Why: Prepare next level nodes to visit in reverse order

Step 3: Traverse level 1 nodes right to left

Level 1: 3 -> 2

Why: Direction flips to right to left for level 1

Step 4: Collect children of level 1 nodes for level 2

Level 2 nodes: 4 -> 5 -> 6

Why: Gather next level nodes for left to right traversal

Step 5: Traverse level 2 nodes left to right

Level 2: 4 -> 5 -> 6

Why: Direction flips back to left to right for level 2

Result:

Zigzag order: [[1], [3, 2], [4, 5, 6]]

Annotated Code

DSA Python

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzag_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True

    while queue:
        level_size = len(queue)
        level_nodes = []
        for _ in range(level_size):
            node = queue.popleft()  # dequeue node for current level
            if left_to_right:
                level_nodes.append(node.val)  # append normally
            else:
                level_nodes.insert(0, node.val)  # insert at front for reverse order
            if node.left:
                queue.append(node.left)  # enqueue left child
            if node.right:
                queue.append(node.right)  # enqueue right child
        result.append(level_nodes)  # add current level to result
        left_to_right = not left_to_right  # flip direction for next level
    return result

# Driver code to test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print(zigzag_level_order(root))

node = queue.popleft() # dequeue node for current level

remove node from front of queue to process current level

if left_to_right: level_nodes.append(node.val) # append normally else: level_nodes.insert(0, node.val) # insert at front for reverse order

add node value in order depending on current direction

if node.left: queue.append(node.left) # enqueue left child if node.right: queue.append(node.right) # enqueue right child

add children to queue for next level traversal

left_to_right = not left_to_right # flip direction for next level

toggle traversal direction for zigzag pattern

Output

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

Complexity Analysis

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

Space: O(n) because the queue can hold up to all nodes at the widest level

vs Alternative: Compared to normal level order traversal, this adds a small overhead inserting at front for reverse order but still remains O(n)

Edge Cases

Empty tree

Returns empty list immediately

DSA Python

if not root:
    return []

Single node tree

Returns list with one level containing the single node

DSA Python

while queue:

Tree with only left or only right children

Traverses levels correctly alternating direction even if some children are missing

DSA Python

if node.left:
    queue.append(node.left)
if node.right:
    queue.append(node.right)

When to Use This Pattern

When you need to traverse a tree level by level but alternate the order of nodes each level, use zigzag level order traversal to capture this pattern.

Common Mistakes

Mistake: Appending nodes always in left to right order without reversing on alternate levels
Fix: Insert nodes at the front of the list on alternate levels to reverse order

Mistake: Not toggling the direction flag after each level
Fix: Flip the left_to_right boolean after processing each level

Summary

It visits tree nodes level by level, alternating direction each level to create a zigzag pattern.

Use it when you want to print or process tree nodes in a zigzag or spiral order.

The key insight is to toggle the direction each level and insert nodes accordingly to reverse order on alternate levels.

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