AlgoMaster Logo

Binary Tree Zigzag Level Order Traversal

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We need to perform a level order traversal of a binary tree, alternating the reading direction at each level. Level 0 goes left to right, level 1 goes right to left, level 2 goes left to right again, and so on. The result is a "zigzag" pattern through the tree.

This is a direct extension of standard level order traversal (LeetCode #102). The traversal itself does not change; every other level is reversed in the output. The approaches below differ only in how they pay for that reversal: an explicit reverse on odd levels, order-aware insertion during BFS, or the same insertion during DFS.

Key Constraints:

  • Number of nodes in range [0, 2000] → Any O(n) traversal is fast at this size. The bound matters for recursion depth: a fully skewed tree puts the DFS approach 2,000 calls deep, which exceeds Python's default recursion limit of 1,000.
  • -100 <= Node.val <= 100 → Node values can be negative. This doesn't affect the traversal logic, but don't assume positive values in your code.
  • The tree can be empty (0 nodes), so handle the null root case.

Approach 1: BFS with Level Reversal

Intuition

Run a standard BFS level order traversal and reverse every odd-numbered level before adding it to the result. Even levels (0, 2, 4, ...) stay left to right; odd levels (1, 3, 5, ...) get reversed to read right to left. A boolean flag leftToRight toggles after each level.

BFS groups nodes by level by recording the queue size before processing: the next levelSize dequeues all belong to the current level, and every child enqueued during them belongs to the next. Each value is collected once and swapped at most once during a reversal, so the reversal step adds O(n) work across the whole traversal.

Algorithm

  1. If the root is null, return an empty list.
  2. Create a queue and add the root. Set a flag leftToRight = true.
  3. While the queue is not empty:
    • Record levelSize = queue.size().
    • Create a list for the current level.
    • Process levelSize nodes: dequeue each, add its value to the current level list, enqueue its non-null children.
    • If leftToRight is false, reverse the current level list.
    • Add the current level list to the result.
    • Toggle leftToRight.
  4. Return the result.

Example Walkthrough

1Start BFS: enqueue root (3), leftToRight=true
3visit920157
1/6

Code

The reversal pass is cheap but avoidable. The next approach places each value in its final position at the moment its node is dequeued.

Approach 2: BFS with Deque Insertion (Optimal)

Intuition

Instead of reversing after collecting, build each level's list in its final order: append values to the end on left-to-right levels, insert them at the front on right-to-left levels. The BFS itself is unchanged; only the destination of each value depends on the direction.

A deque (double-ended queue) supports O(1) insertion at both ends. On an odd level, the first node dequeued is the leftmost, and every later prepend pushes it further toward the back, so the finished deque reads right to left with no explicit reversal. And because levelSize is known before a level is processed, a plain array works as well: write the i-th dequeued value to index i on left-to-right levels and to index levelSize - 1 - i on right-to-left levels.

Algorithm

  1. If the root is null, return an empty list.
  2. Create a queue and add the root. Set a flag leftToRight = true.
  3. While the queue is not empty:
    • Record levelSize = queue.size().
    • Create a deque for the current level.
    • Process levelSize nodes:
      • Dequeue a node.
      • If leftToRight, add the value to the end of the level deque.
      • If not leftToRight, add the value to the front of the level deque.
      • Enqueue non-null children.
    • Convert the level deque to a list and add it to the result.
    • Toggle leftToRight.
  4. Return the result.

Example Walkthrough

1Start BFS: enqueue root (3), leftToRight=true
3visit920157
1/7

Code

Both approaches so far are BFS. The same output can also come from DFS, with the recursion stack standing in for the explicit queue.

Approach 3: DFS with Level Tracking

Intuition

A preorder DFS that carries the current depth produces the same per-level grouping as BFS. When the traversal reaches a node at level d, its value goes into result[d]: appended to the end on even levels, inserted at the front on odd levels.

This produces correct zigzag order because preorder DFS with left-before-right recursion visits the nodes of any given level in left-to-right order, the same order BFS would. Appending preserves that order on even levels, and front insertion reverses it on odd levels.

The recursion stack replaces the explicit queue, but it brings its own constraint: the stack grows to the height of the tree. A fully skewed tree with 2,000 nodes means a call depth of 2,000, past Python's default recursion limit of 1,000. The BFS approaches have no such limit.

Algorithm

  1. Create an empty list of lists called result.
  2. Define a recursive function dfs(node, level):
    • If node is null, return. This also covers the empty tree.
    • If level equals the size of result, add a new empty list (first time visiting this level).
    • If level is even, append node.val to result[level].
    • If level is odd, insert node.val at the front of result[level].
    • Recurse on the left child with level + 1.
    • Recurse on the right child with level + 1.
  3. Call dfs(root, 0) and return result.

With a plain array as the level container, front insertion shifts every element already in the level. In that case, append on every level and reverse the odd levels once after the traversal finishes; the result is identical and the total work stays O(n).

Example Walkthrough

1Start DFS at root (3), level=0 (even → append)
3visit920157
1/6

Code