Binary Tree Zigzag Level Order Traversal

Intuition

The tree is still explored strictly top to bottom, left to right; only the final arrangement of each level alternates. So we keep the standard queue-based level-order sweep and add a boolean flag that flips after every level. When the flag says left to right we append values normally, and when it says right to left we insert them at the front (or compute a mirrored index) so the level ends up reversed. Deciding placement while collecting avoids a separate reversal pass and keeps the logic to a single loop per level.

Algorithm walkthrough

1. 1Return an empty list if the root is null; otherwise seed a queue with the root and set the direction flag to left-to-right.
2. 2While the queue is not empty, capture its size as the number of nodes on the current level.
3. 3For each node on the level, dequeue it and place its value at the front or back of the level list according to the flag.
4. 4Enqueue each node's non-null children so they form the next level in normal left-to-right order.
5. 5Append the finished level to the result and flip the direction flag.
6. 6When the queue empties, return the list of levels.

Implementation

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue: deque = deque([root])
        left_to_right = True
        while queue:
            level_size = len(queue)
            level: List[int] = []
            for _ in range(level_size):
                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