Problem Statement

Binary Tree Zigzag Level Order Traversal

You are given the top node (the root) of a binary tree. A binary tree is a structure where each node can point to a left child and a right child, like a family tree that only ever splits in two. Your job is to read the tree one level at a time, but the direction zigzags. The first level (the root by itself) is read left to right. The next level down is read right to left. The level after that goes left to right again, and so on, flipping each time. Return a list of lists, where each inner list holds one level's values in the right order.

mediumTreeBFSTreesTime: O(n) · Space: O(n)

Signals to notice

level order but alternating directionleft-to-right then right-to-leftzigzag pattern

Brute force first

Level order traversal then reverse every other level — but requires post-processing. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

BFS with a flag that alternates each level. On even levels, append normally. On odd levels, prepend (or reverse the level array). Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `root = [3,9,20,null,null,15,7]`

init: queue=[3], result=[], ltr=True
Level 0: size=1, pop 3 -> level=[3], enqueue 9,20 -> queue=[9,20]. ltr=True -> append [3]. result=[[3]], ltr=False
Level 1: size=2, pop 9 -> level=[9] (9 has no children), pop 20 -> level=[9,20], enqueue 15,7 -> queue=[15,7]
Level 1 emit: ltr=False -> reverse [9,20] = [20,9]. result=[[3],[20,9]], ltr=True
Level 2: size=2, pop 15 -> level=[15] (no children), pop 7 -> level=[15,7] (no children) -> queue=[]
Level 2 emit: ltr=True -> append [15,7]. result=[[3],[20,9],[15,7]], ltr=False
queue empty -> return [[3],[20,9],[15,7]]

What must stay true

The BFS queue always processes nodes left-to-right. The zigzag effect comes from how you ADD the results to the level array — prepend on odd levels to reverse the apparent order. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

queue = [root]; result = []; ltr = true
while queue not empty:
    size = len(queue); level = []
    repeat size times: pop node -> level.append(node.val); push node.left, node.right
    result.append(ltr ? level : reverse(level)); ltr = not ltr
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Trying to change the queue processing order — that's complex. Easier to always process left-to-right and just reverse the output for alternate levels. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Trees Pattern