Binary Tree Zigzag Level Order Traversal: BFS with Alternating Direction

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. That means collecting values left to right for the first level, then right to left for the next, then left to right again, and so on. This is LeetCode 103: Binary Tree Zigzag Level Order Traversal.

For example, given root = [3, 9, 20, null, null, 15, 7], the output is [[3], [20, 9], [15, 7]].

Approach

If you already know how to do a standard level order traversal (LeetCode 102), zigzag is a small twist on top. The core idea is the same: use BFS with a queue, snapshot the queue size at the start of each level, and drain exactly that many nodes. The only addition is a direction flag that alternates after every level.

There are two clean ways to handle the direction flip:

1. Collect then reverse. Run normal BFS left to right. After collecting a level, check if the level index is odd. If so, reverse the level list before appending it to the result.
2. Use a deque for each level list. Instead of always appending to the right, alternate between append and appendleft depending on the direction flag. This avoids the explicit reverse.

Both approaches are O(n) overall. The reverse approach is simpler to reason about because the BFS logic stays untouched. That is the version shown below.

The Python solution

from collections import deque

def zigzag_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True
    while queue:
        level_size = len(queue)
        level = deque()
        for _ in range(level_size):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(list(level))
        left_to_right = not left_to_right
    return result

Here is what each part does:

• left_to_right = True tracks the current direction. It starts as True because level 0 reads left to right.
• level = deque() holds the current level's values. Using a deque lets you insert at either end in O(1).
• level.append vs level.appendleft controls the output order. When left_to_right is true, values go to the right end (normal order). When false, values go to the left end (reversed order).
• left_to_right = not left_to_right flips the direction after each level finishes.

The BFS itself never changes. You always dequeue from the left and enqueue children left then right. Only the output insertion direction alternates.

Visual walkthrough

Trace through the tree [3, 9, 20, null, null, 15, 7]. Pay attention to how the direction flips at each level and how that changes the order of values in the output.

The queue always processes nodes in the same order (left to right within each level). The zigzag effect comes entirely from how you insert values into the level list. On even levels you append to the right. On odd levels you append to the left, which effectively reverses the order without an extra pass.

Complexity analysis

The deque-based insertion (append or appendleft) is O(1) per operation, so using it instead of a list reverse does not change the overall time complexity. Even the reverse approach is O(n) total because the sum of all level sizes is n.

Building blocks

This problem is built on one core pattern: BFS level-by-level processing with a direction flag.

from collections import deque

def bfs_zigzag(root):
    queue = deque([root])
    left_to_right = True
    while queue:
        level_size = len(queue)
        level = deque()
        for _ in range(level_size):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            for child in [node.left, node.right]:
                if child:
                    queue.append(child)
        left_to_right = not left_to_right

The level_size = len(queue) snapshot separates levels. The left_to_right boolean controls output direction. Together they form the complete zigzag template.

This same direction-flag technique appears whenever you need to alternate behavior across BFS levels. Once you have the standard level-order BFS template internalized, adding the flag is mechanical.

Edge cases

• Empty tree (root is None): return an empty list []. The guard clause at the top handles this.
• Single node (no children): return [[root.val]]. Only level 0 exists, which reads left to right. The flag never flips.
• Left-only tree (every node has only a left child): each level has one node, so the zigzag reversal has no visible effect. The result is [[a], [b], [c], ...].
• Right-only tree (every node has only a right child): identical behavior to the left-only case. One node per level means reversal is a no-op.

From understanding to recall

You just traced through a zigzag BFS and saw that the only difference from standard level order is a direction flag. It feels obvious now. But in an interview next month, will you remember whether to flip the flag before or after appending the level? Will you recall that appendleft on a deque gives you the reversal for free?

Reading a solution is not the same as reproducing it under time pressure. Spaced repetition closes that gap. You practice typing the BFS zigzag template from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the flag flip, the deque trick, and the level snapshot until the pattern is automatic.

BFS with a direction flag is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - The base BFS level-by-level pattern that this problem builds on
• Maximum Depth of Binary Tree - Tree recursion fundamentals, plus a BFS alternative that counts levels