Binary Tree Zigzag Level Order Traversal | Leetcode 103 | BFS with Direction Switching

You are given the root of a binary tree. You need to return the zigzag level order traversal of its nodes’ values.

• In normal level order traversal (BFS), nodes at each level are visited from left to right.
• In zigzag level order traversal, the direction alternates:
  • First level left → right
  • Second level right → left
  • Third level left → right
  • and so on…

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]

        3
       / \
      9   20
         /  \
        15   7

Output: [[3],[20,9],[15,7]]

Example 2

Input: root = [1]

Output: [[1]]

Example 3

Input: root = []

Output: []

Intuition and Approach

This problem is a small variation of standard BFS traversal:

1. Use a queue (like in level order traversal) to process nodes level by level.
2. Maintain a flag flag that tracks traversal direction:
   • flag == 0 → left to right
   • flag == 1 → right to left
3. For each level:
   • Create an array ans of size equal to the level.
   • While processing nodes, insert values at the correct index:
     • If flag == 0, put values at index i (normal order).
     • If flag == 1, put values at level_size - i - 1 (reverse order).
4. After processing a level, flip the flag for the next level.
5. Continue until the queue is empty.

This ensures that levels alternate between left-to-right and right-to-left traversal.

Code Implementation

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = deque()
        flag = 0
        queue.append(root)
        result = []
        while queue:
            level_size = len(queue)
            ans = [-1] * level_size
            for i in range(level_size):
                node = queue.popleft()
                if flag == 1:
                    index = level_size - i - 1
                else:
                    index = i
                ans[index] = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if flag == 0:
                flag = 1
            else:
                flag = 0
            result.append(ans)
        return result

Code Explanation

• Queue Initialization: Start with the root node in the queue.
• flag: Determines current direction (0 = left→right, 1 = right→left).
• Processing a Level:
  • Use level_size to process all nodes of the current level.
  • Compute the correct index for each node’s value based on flag.
  • Push child nodes (left, then right) into the queue for the next level.
• Flipping Direction: After each level, toggle flag to reverse the direction.
• Result Collection: Append the filled ans array for each level into result.

Dry Run

Consider input: [3,9,20,null,null,15,7]

Level 0: [3] → flag=0 → ans=[3]
Level 1: [9,20] → flag=1 → ans=[20,9]
Level 2: [15,7] → flag=0 → ans=[15,7]

Final Output: [[3],[20,9],[15,7]]

Time and Space Complexity

• Time Complexity:
  Every node is visited once → O(N), where N = number of nodes.
• Space Complexity:
  Queue can hold at most one level’s worth of nodes, so in worst case O(N).

Conclusion

The zigzag level order traversal is simply a modification of BFS where we alternate the insertion order at each level. By using a queue for level order traversal and a flag to reverse order alternately, we can efficiently achieve the zigzag pattern.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.