← DSA Atlas
Dedicated problem page · #103

Binary Tree Zigzag Level Order Traversal

MediumTrees and Binary Search TreesBFS level order with alternating directionQueue-based breadth-first traversal
Solve on LeetCode ↗
103
MediumTrees and Binary Search TreesQueue-based breadth-first traversalBFS level order with alternating direction

Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its node values: left-to-right on the first level, right-to-left on the next, alternating for each subsequent level.

Open official problem prompt ↗
In plain English

Output the tree's values grouped by depth, but read each level in an alternating boustrophedon (zigzag) direction.

Picture it like this

Like reading a scroll written boustrophedon style — the first line left-to-right, the next right-to-left, snaking back and forth down the page.

Example
Input
root = [3, 9, 20, null, null, 15, 7]
Output
[[3], [20, 9], [15, 7]]
Why
Level 0 = [3] left-to-right; level 1 read right-to-left = [20, 9]; level 2 left-to-right = [15, 7].
Constraints
The number of nodes is in the range [0, 2000]-100 <= Node.val <= 100
Pattern lesson

See the pattern, then code

BFS level order with alternating direction
Recognition clue

Grouping output by depth points to BFS; the alternating left/right reading order per level is what turns plain level-order into zigzag.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Do a normal BFS level by level, but reverse how you record every other level. Appending to the front of a deque cheaply produces the reversed order without reversing a list afterward.

New words, made simpleKnow these before the algorithm
Level order (BFS)
Visiting all nodes at depth d before any at depth d+1, using a queue.
Deque
A double-ended queue allowing O(1) appends at both front and back.
Direction flag
A boolean that toggles each level to decide front vs back insertion.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
BFS then reverse odd levels

Correct and readable; the reversal is a minor extra pass per level.

Collect each level normally, then reverse the lists at odd depths.

Time O(n)Space O(n)
Best choiceBFS with deque front-insertion

Avoids explicit reversal and keeps children enqueued in normal order.

Insert into a deque's front on reversed levels so the order is built directly.

Time O(n)Space O(n)
The rule we keep true

Invariant

At the start of each while iteration the queue holds exactly the nodes of one depth, in left-to-right order; the flag says how to read that depth.

Why this is correct

Reasoning

Children are always enqueued left-to-right, so the queue naturally presents each level left-to-right. The zigzag effect is purely a recording choice: on reversed levels we push values to the front of the deque, yielding right-to-left output while traversal order stays consistent and correct.

The algorithm in three movesSay these aloud before coding
1Push the root into a queue and initialize a direction flag

level 0: [3], flip

2For each level, pop exactly the current level's count of nodes

level 1 (R->L): appendleft 9 then 20 -> [20,9]

3Append each value to the back or front of a deque based on direction

level 2 (L->R): [15,7]

4Enqueue children left-then-right, flip the direction, and store the level

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
91
202
153
74
1 · Readqueue=[3], L->R
2 · Askrecord
3 · Update statelevel=[3]
4 · Resultenqueue 9,20; flip to R->L
Key takeaway

Each BFS level is recorded, reversing direction on alternate depths.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Empty guard

    No root means an empty result list.

  2. 2
    Lines 8-9Level loop setup

    Snapshot len(queue) so we process exactly the current depth's nodes.

  3. 3
    Lines 10-14Direction-aware record

    Append to back for L->R levels, to front for R->L levels.

  4. 4
    Lines 15-18Enqueue children

    Always left then right so the queue stays in natural order.

  5. 5
    Lines 19-20Store and flip

    Save the level and toggle direction for the next depth.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty tree -> []
  • Single node -> [[val]]
  • Completely skewed tree still yields one node per level
!

Common beginner mistakes

  • Using len(queue) inside the loop after it changes instead of snapshotting it first
  • Reversing the traversal order of children rather than just the recording order
  • Forgetting to flip the direction flag each level
Check your understanding

Why keep enqueuing children left-to-right even on right-to-left levels?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split