Zigzag Level Order Traversal in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Level Order Traversal on a small tree

What is the output of the zigzag level order traversal for the given binary tree?

DSA Python

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

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    current_level = [root]
    left_to_right = True
    while current_level:
        level_values = []
        next_level = []
        for node in current_level:
            level_values.append(node.val)
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        if not left_to_right:
            level_values.reverse()
        result.append(level_values)
        current_level = next_level
        left_to_right = not left_to_right
    return result

# Tree structure:
#       1
#      / \
#     2   3
#    /     \
#   4       5

root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, None, TreeNode(5)))
print(zigzagLevelOrder(root))

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

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

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

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

💡 Hint

Remember that the traversal direction alternates at each level.

The traversal starts left to right at level 0: [1].

At level 1, it goes right to left: [3, 2].

At level 2, it goes left to right again: [4, 5].

❓ Predict Output

intermediate

Zigzag traversal output for a single node tree

What is the output of zigzag level order traversal for a tree with only one node?

DSA Python

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

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    current_level = [root]
    left_to_right = True
    while current_level:
        level_values = []
        next_level = []
        for node in current_level:
            level_values.append(node.val)
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        if not left_to_right:
            level_values.reverse()
        result.append(level_values)
        current_level = next_level
        left_to_right = not left_to_right
    return result

root = TreeNode(10)
print(zigzagLevelOrder(root))

A [[10]]

B []

C [[], [10]]

D [[10], []]

💡 Hint

A single node tree has only one level.

Since there is only one node, the traversal returns a list with one list containing that node's value.

🔧 Debug

advanced

Identify the error in zigzag traversal code snippet

What error will this code raise when run?

DSA Python

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    current_level = [root]
    left_to_right = True
    while current_level:
        level_values = []
        next_level = []
        for node in current_level:
            level_values.append(node.val)
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        if left_to_right:
            level_values.reverse()
        result.append(level_values)
        current_level = next_level
        left_to_right = not left_to_right
    return result

# Tree with root only
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root = TreeNode(1)
print(zigzagLevelOrder(root))

A The output is [[1]]

B The output is [[1]] but reversed incorrectly

C The output is [[]]

D No output, infinite loop

💡 Hint

Check the condition that controls when to reverse the level values.

The code reverses the level values when left_to_right is True, but it should reverse when left_to_right is False.

This causes the first level to be reversed incorrectly.

🧠 Conceptual

advanced

Why use two data structures in zigzag traversal?

In zigzag level order traversal, why do we use two lists (or queues) to keep track of nodes at the current and next level?

A To avoid recursion and use only iterative approach

B To store nodes in ascending and descending order simultaneously

C To separate nodes by their depth levels and control traversal direction per level

D To keep track of visited and unvisited nodes separately

💡 Hint

Think about how levels are processed one by one.

Two lists help process nodes level by level and allow reversing the order of values at alternate levels.

🚀 Application

expert

Zigzag traversal output for a complex tree

What is the output of zigzag level order traversal for this tree? # Tree structure: # 10 # / \ # 6 15 # / \ \ # 3 8 20 # / / \ # 7 17 25

DSA Python

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

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    current_level = [root]
    left_to_right = True
    while current_level:
        level_values = []
        next_level = []
        for node in current_level:
            level_values.append(node.val)
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        if not left_to_right:
            level_values.reverse()
        result.append(level_values)
        current_level = next_level
        left_to_right = not left_to_right
    return result

root = TreeNode(10,
                TreeNode(6, TreeNode(3), TreeNode(8, TreeNode(7))),
                TreeNode(15, None, TreeNode(20, TreeNode(17), TreeNode(25))))

print(zigzagLevelOrder(root))

A [[10], [15, 6], [3, 8, 20], [25, 17, 7]]

B [[10], [6, 15], [3, 8, 20], [7, 17, 25]]

C [[10], [6, 15], [20, 8, 3], [7, 17, 25]]

D [[10], [15, 6], [3, 8, 20], [7, 17, 25]]

💡 Hint

Remember the traversal direction flips every level starting left to right at root.

Level 0 (left to right): [10]

Level 1 (right to left): [15, 6]

Level 2 (left to right): [3, 8, 20]

Level 3 (right to left): [7, 17, 25] reversed to [25, 17, 7] but since direction is right to left, we reverse the collected values, so output is [7, 17, 25].

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