Binary Tree Zigzag Level Order Traversal — LC 103 BFS Pattern Interview Guide

Problem Statement#

Given the root of a binary tree, return the zigzag level order traversal of node values: level 0 left-to-right, level 1 right-to-left, alternating thereafter.

Constraints:

• Number of nodes is in range 0 to 2000
• Node values fit in int range from -100 to 100
• Tree may be empty

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

Input:  root = [1,2,3,4,null,null,5]
Output: [[1],[3,2],[4,5]]

Why This Problem Matters#

LeetCode 103 Binary Tree Zigzag Level Order Traversal is a Medium-tier classic that appears regularly in Amazon, Meta, Microsoft, Bloomberg, and Adobe interviews. It is the canonical follow-up to LC 102 Level Order Traversal — interviewers ask LC 102 first, then add the zigzag twist to see whether the candidate can adapt rather than rewrite.

The problem measures three skills: BFS template fluency, deque vs list awareness, and the discipline to toggle state at the right scope. Many candidates fail because they flip the direction inside the inner per-node loop instead of after the level completes, or because they reverse the enqueue order of children which breaks the next level entirely.

In real systems, zigzag-style ordering shows up in UI rendering of alternating row layouts, boustrophedon printer paths, and certain cache-friendly matrix scans. In interviews, it is a vehicle for discussing when a deque outperforms a list and how to keep traversal logic separate from output formatting.

The Core Insight#

The traversal itself never changes. We always do standard BFS and always enqueue the left child before the right child. The only thing that alternates is how we record the values for each level: left-to-right levels append to the back of a buffer, right-to-left levels prepend to the front.

Using a deque for the per-level buffer makes both append and appendleft O(1). Toggling a single boolean after each level completes gives us correct alternation without any extra reversals. This separates traversal order from output order — a clean abstraction interviewers value.

The flag must flip exactly once per level, never per node. The natural place is right after the inner for-loop finishes processing all nodes at the current depth.

Visual Dry Run#

Tree: root=3, left=9, right=20, 20.left=15, 20.right=7.

Children are always enqueued left-then-right. Only the per-level buffer order alternates.

Solution (Optimal)#

from collections import deque
 
class Solution:
    def zigzagLevelOrder(self, 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

var zigzagLevelOrder = function(root) {
    if (!root) return [];
 
    const result = [];
    const queue = [root];
    let leftToRight = true;
 
    while (queue.length > 0) {
        const levelSize = queue.length;
        const level = [];
 
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (leftToRight) {
                level.push(node.val);
            } else {
                level.unshift(node.val);
            }
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
 
        result.push(level);
        leftToRight = !leftToRight;
    }
 
    return result;
};

Time: O(n) — every node is enqueued and dequeued exactly once. Space: O(w) — w is the maximum width of the tree, which is the queue's peak size.

Common Mistakes#

• Flipping the direction flag inside the per-node loop instead of after the level completes
• Using list.insert(0, val) which is O(n) per call instead of deque.appendleft which is O(1)
• Reversing the order children are enqueued, which corrupts the next level
• Forgetting if not root: return [] which crashes when enqueuing None
• Returning the deque object itself instead of list(level) in the result

Interview Tips#

• Start by writing standard LC 102 BFS, then add the toggle — show your incremental thinking
• Explicitly say "the traversal order does not change, only the storage direction" — this signals senior-level decomposition
• Mention deque vs list tradeoffs even if the input size does not require it
• Discuss the DFS alternative briefly (track depth, append or prepend by depth parity) but recommend BFS

Follow-up Questions#

• Zigzag for an N-ary tree (LC 429 variant) — same pattern, enqueue all children in order
• Print only odd-indexed levels — gate the result.append with the flag
• Bottom-up zigzag — same code, reverse the final result
• Zigzag with column index output — track column with the node and group by column

Key Takeaways#

• LeetCode 103 Binary Tree Zigzag Level Order is a Medium BFS problem, frequently asked at Amazon, Meta, Microsoft, and Bloomberg
• Time complexity is O(n) where n is the number of nodes; space is O(w) for the BFS queue
• The optimal pattern uses collections.deque with appendleft for O(1) prepend
• Always enqueue left child before right child; only toggle the storage direction
• The boolean flag must flip after each level, never per node
• Using list.insert(0, val) instead of deque.appendleft degrades the solution to O(n*w) on wide trees
• Same template solves LC 102 Level Order, LC 107 Bottom-Up Level Order, and LC 199 Right Side View