Binary Tree Zigzag Level Order Traversal (LeetCode 103)

The problem

You get the root of a binary tree. Return its values level by level, but alternate direction: level 0 left to right, level 1 right to left, level 2 left to right again, and so on.

Input:      3
           / \
          9   20
             /  \
            15   7

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

Level 1 is read right to left, so 20 comes before 9.

How to think about it

Start with the tempting wrong idea. Change the order you push children: on odd levels push right before left. That messes up the next level. The queue order then no longer matches the tree’s left-to-right layout, and two levels down the output is scrambled.

Simple fix that works: do the ordinary level-order traversal, then reverse every odd level. That’s correct and O(n), just an extra pass over half the levels.

The key insight: keep the traversal normal and change only where each value lands. The queue keeps visiting every level left to right, exactly as in LeetCode 102. For each level, collect values into a deque: on left-to-right levels append (add to the back); on right-to-left levels appendleft (add to the front). Adding to the front in left-to-right visiting order produces the reversed list, with no separate reverse step. Flip a boolean ltr after each level.

Which pattern is this? Tree BFS. The tell is “level order” plus a twist on how each level is presented. Separate “how you traverse” from “how you record”.

Approach

1. If root is None, return [].
2. Start a queue with root and set ltr = True.
3. While the queue is not empty:
   • create an empty deque level,
   • pop len(q) nodes; for each, append its value if ltr, otherwise appendleft; push its left then right child,
   • append list(level) to res and flip ltr.
4. Return res.

Solution

from collections import deque

def zigzag(root):
    if not root: return []
    res = []; q = deque([root]); ltr = True
    while q:
        level = deque()
        for _ in range(len(q)):
            n = q.popleft()
            if ltr: level.append(n.val)           # left to right: add at the back
            else: level.appendleft(n.val)         # right to left: add at the front
            if n.left: q.append(n.left)           # traversal order never changes
            if n.right: q.append(n.right)
        res.append(list(level)); ltr = not ltr
    return res
# zigzag([3,9,20,null,null,15,7]) -> [[3],[20,9],[15,7]]

Dry run

On the example tree:

Result: [[3], [20, 9], [15, 7]].

Complexity

• Time: O(n). Each node is pushed and popped once, and append/appendleft on a deque are O(1).
• Space: O(w) for the queue and the current level, where w is the widest level; O(n) in the worst case, plus the output.

Edge cases and pitfalls

• Empty tree: returns [].
• Single node: [[root.val]].
• Changing child push order instead of the recording order breaks deeper levels.
• list.insert(0, x) for right-to-left levels is O(w) per insert, so O(w²) per level. The deque avoids that.
• Forgetting to flip ltr gives plain level order.

Related problems

• Binary Tree Level Order Traversal (LeetCode 102): the unchanged traversal underneath.
• Binary Tree Level Order Traversal II (LeetCode 107): flips the order of levels instead of within them.
• Sliding Window Maximum (LeetCode 239): another problem where a deque’s O(1) work at both ends is the point.