Zigzag Level Order Traversal LeetCode 103

LeetCode 103, Binary Tree Zigzag Level Order Traversal, asks you to return the level order traversal of a binary tree's values but in a zigzag pattern: the first level goes left to right, the second level goes right to left, the third goes left to right again, and so on. The result is a list of lists, each inner list containing the values for one level.

For a tree with root 3, left child 9, right child 20, and 20's children 15 and 7, the expected output is [[3], [20, 9], [15, 7]]. The root level is left-to-right (just [3]), the second level is right-to-left ([20, 9]), and the third level is left-to-right again ([15, 7]).

This is a direct extension of LeetCode 102 Binary Tree Level Order Traversal. If you can solve 102, solving 103 requires only one extra step: tracking a direction flag and reversing (or deque-prepending) alternate levels. It is a common interview problem at Amazon, Microsoft, and Bloomberg.

The standard approach is to run a normal level-order BFS with a queue. After collecting all values for a level, check the direction flag. If the current direction is right-to-left, reverse the collected values before appending them to the result. Then toggle the flag for the next level.

The key insight is that BFS naturally gives you one full level at a time when you snapshot the queue size at the start of each level iteration. Process exactly that many nodes, collect their values, add their children to the queue, and then either append the values directly or append the reversed values depending on the flag.

This approach is clean, easy to explain in an interview, and directly extends LeetCode 102 with a single boolean and a conditional reverse. The reversal is O(w) where w is the width of the level, and the total work across all levels is O(n) since every node is visited exactly once.

Initialize a queue with the root node and a boolean leftToRight set to true. On each iteration of the outer while loop, read the current queue size — this is the number of nodes in the current level. Use an inner for loop to dequeue exactly that many nodes, collect their values, and enqueue their non-null children.

After the inner loop finishes, if leftToRight is false, reverse the collected level values. Append the (possibly reversed) values to the result list. Toggle leftToRight and continue to the next level. This processes the entire tree in O(n) time and O(n) space for the queue and result.

Edge cases: if root is null, return an empty list immediately. If a node has only a left or only a right child, only that child is enqueued — the BFS handles sparse trees naturally without any special casing.

Instead of collecting level values into a list and reversing, you can collect them into a deque (double-ended queue) and choose the insertion end based on the direction flag. If left-to-right, append to the right of the deque. If right-to-left, appendleft to the left of the deque. The deque is then converted to a list before being added to the result.

This approach avoids the explicit reverse call on each odd level. Since deque appendleft is O(1), the per-level work is the same O(w). The total time complexity remains O(n). In Python, collections.deque supports appendleft natively. In Java, ArrayDeque supports addFirst and addLast.

The deque approach can feel more elegant because it processes nodes in the natural BFS order but builds the level output in the correct zigzag order on the fly. However, it introduces the cognitive overhead of tracking which end to insert into, which can lead to bugs if the direction logic is inverted.

A DFS approach using recursion can also solve this problem. Pass a level parameter alongside the node. Maintain the result as a list of lists. When you visit a node at a given level, if that level's list does not yet exist in the result, append a new empty list. Then insert the node's value: if the level is even (left-to-right), append to the end of that level's list; if the level is odd (right-to-left), insert at the front (index 0).

Inserting at index 0 is O(w) for a Python list, so in the worst case (a skewed tree) the DFS approach can be O(n^2). For balanced trees it is fine. In Java, using ArrayDeque for each level and calling addFirst or addLast achieves O(1) insertion either way, restoring O(n) total complexity.

The BFS approach is generally preferred for level-order problems because it naturally processes levels one at a time, making the level grouping explicit. The DFS approach requires careful bookkeeping of the result list size and insertion position, which is more error-prone under interview time pressure.

Python BFS + reverse: from collections import deque; def zigzagLevelOrder(root): if not root: return []; queue = deque([root]); result = []; leftToRight = True; while queue: size = len(queue); level = []; for _ in range(size): node = queue.popleft(); level.append(node.val); if node.left: queue.append(node.left); if node.right: queue.append(node.right); if not leftToRight: level.reverse(); result.append(level); leftToRight = not leftToRight; return result. Time O(n), space O(n).

Java BFS + reverse: public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } if (!leftToRight) Collections.reverse(level); result.add(level); leftToRight = !leftToRight; } return result; }.

Both solutions are direct implementations of the BFS + direction flag approach. The Python version uses collections.deque for O(1) popleft. The Java version uses LinkedList as the queue. Both toggle leftToRight after each level and call reverse on odd-indexed levels. The overall time complexity is O(n) and space complexity is O(n) for the queue and result.

LeetCode 102 Binary Tree Level Order Traversal is the direct predecessor — the same BFS structure without the zigzag direction flag. LeetCode 107 Binary Tree Level Order Traversal II returns the same result but in reverse order (bottom-up). Both are solved with the same BFS template; 107 simply reverses the result list at the end.

LeetCode 199 Binary Tree Right Side View returns only the last node of each level — the node visible from the right side. It uses BFS with the same level-size snapshot, but only appends the last value of each level. LeetCode 513 Find Bottom Left Tree Value returns the first value of the last level, also solvable with BFS by tracking the first node of each level.

Mastering the BFS level-order template unlocks a whole family of tree problems. The template is: initialize queue with root, while queue not empty: snapshot level size, process that many nodes, enqueue children, decide what to record from each level. LeetCode 103 Zigzag adds only the direction toggle on top of this template.