Zigzag Level Order Traversal in DSA Python - Time & Space Complexity

Time Complexity: Zigzag Level Order Traversal

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to traverse a tree in zigzag order changes as the tree grows.

How does the number of nodes affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import deque

def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.insert(0, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
        left_to_right = not left_to_right
    return result
    

This code visits each node level by level, switching direction each level to create a zigzag pattern.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once in a breadth-first manner (O(1) per node).
• Costly operation: When reversing direction, level.insert(0, node.val) shifts all existing elements, costing O(current level size).
• How many times: For a level of size m, reversal costs 1 + 2 + ... + m = O(m²).

How Execution Grows With Input

As the number of nodes (n) grows, visiting nodes is O(n), but reversal costs sum to O(n²) in the worst case (e.g., wide levels).

Input Size (n)	Approx. Operations
10	~10 visits + small reversal shifts (~50 ops)
100	~100 visits + reversal shifts up to ~2500 ops per large level
1000	~1000 visits + reversal shifts up to ~250,000 ops for wide levels

Pattern observation: Dominated by O(n²) due to repeated inserts on large levels.

Final Time Complexity

Time Complexity: O(n^2)

The BFS is O(n), but insert(0) on levels of size up to O(n) leads to quadratic time overall.

Common Mistake

[X] Wrong: "We visit each node once, so it's O(n)."

[OK] Correct: Ignores that insert(0) costs O(level size) each time. For a level of m nodes, total shift cost is O(m²). Large levels make it quadratic.

Interview Connect

Spotting inefficient list operations like insert(0) shows deep understanding. Interviewers value suggesting fixes like reversing the level list at the end (O(n total)) or using a deque.

Self-Check

"What if we used a deque for the level, appending left when reversing? Or reversed the level list once at the end? How would the time complexity change to O(n)?"

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