Zigzag Level Order Traversal in DSA Python - Build from Scratch

Zigzag Level Order Traversal

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to visit each generation, but in a zigzag pattern: left to right on one level, then right to left on the next, and so on. This helps you see the family members in a fun, alternating order.

🎯 Goal: Build a program that takes a binary tree and prints the values of nodes level by level, but alternates the direction of traversal for each level (zigzag order).

📋 What You'll Learn

Create a binary tree using the TreeNode class with the exact structure given.

Create a variable result to store the zigzag level order traversal.

Use a while loop to traverse the tree level by level.

Use a boolean variable left_to_right to switch traversal direction each level.

Print the final result list.

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in scenarios like printing organizational charts, family trees, or any hierarchical data where alternating the direction of reading improves readability.

💼 Career

Understanding tree traversals and how to manipulate traversal order is important for software engineers working with hierarchical data structures, UI trees, or algorithms involving graphs and trees.

1

Create the binary tree

Create the binary tree using the TreeNode class with this exact structure: root node value 1, left child 2, right child 3, left child of 2 is 4, right child of 2 is 5, left child of 3 is 6, right child of 3 is 7.

DSA Python

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

# Create the binary tree nodes and link them
# Your code here

Hint

Start by creating the root node with value 1. Then create its left and right children with values 2 and 3. Continue linking the children as described.

2

Initialize variables for traversal

Create a list called result to store the final zigzag order. Create a list called current_level containing only the root node. Create a boolean variable left_to_right and set it to True to track traversal direction.

DSA Python

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

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# Initialize result list, current_level list, and left_to_right boolean
# Your code here

Hint

Use an empty list for result. Put the root node inside a list called current_level. Set left_to_right to True to start from left to right.

3

Traverse the tree in zigzag order

Use a while loop that runs while current_level is not empty. Inside the loop, create a list level_values with the values of nodes in current_level. If left_to_right is False, reverse level_values. Append level_values to result. Create a new list next_level containing all non-None children of nodes in current_level. Set current_level to next_level. Flip the boolean left_to_right to its opposite value.

DSA Python

while current_level:
    level_values = [node.val for node in current_level]
    if not left_to_right:
        level_values.reverse()
    result.append(level_values)
    next_level = []
    for node in current_level:
        if node.left:
            next_level.append(node.left)
        if node.right:
            next_level.append(node.right)
    current_level = next_level
    left_to_right = not left_to_right
# Print the result

Hint

Use a while loop to process each level. Extract values, reverse if needed, add to result, then prepare the next level nodes. Flip the direction boolean at the end of each loop.

4

Print the zigzag traversal result

Print the result list to display the zigzag level order traversal of the tree.

DSA Python

Hint

Use print(result) to show the final zigzag traversal list.

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