Difficulty: MediumTrees

Binary Tree Zigzag Level Order Traversal

Problem in Plain English

Given the root of a binary tree, return its values level by level while alternating direction on every level: even levels run left to right and odd levels run right to left. An empty tree returns an empty list.

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its node values.

Level 0 is read left to right, level 1 is read right to left, level 2 is read left to right again, and the direction keeps alternating. Return one list per level, or an empty list when root is null.

Constraints

The tree contains between 0 and 2000 nodes, inclusive.
Each node value is between -100 and 100, inclusive.

Examples

Example 1

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

Level 0 gives [3], level 1 is reversed to [20,9], and level 2 stays [15,7].

Example 2

Input: root = [1]
Output: [[1]]

A single node forms one level read left to right.

Example 3

Input: root = []
Output: []

An empty tree has no levels, so the answer is an empty list.

Example 4

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

Reverse the second level to [3,2], but keep discovering children through parents 2 then 3. This makes the third level [4,5,6], rather than [5,6,4]. Missing children do not add output placeholders.

Intuition

Separate which nodes belong to a depth from which direction their values are displayed. A queue discovers each depth left to right; only the output changes direction. In Example 1, visit 9 before 20 to discover their children correctly, but display that level as [20,9]. The next level still displays [15,7].

Approaches

BFS Then Reverse

Solution Details

Reveal BFS Then Reverse: intuition, complexity, and code

Intuition

Use ordinary left-to-right breadth-first search to assemble each level, then reverse every other completed level. The queue keeps its discovery order throughout; reversing a list of values cannot disrupt the order of future children.

Step-by-Step Logic

Return an empty result for a null root; otherwise enqueue the root and set the direction to left to right. Example 1 begins with queue [3].
Before each level, save its queue size. Process exactly that many nodes, recording each value and adding non-null left then right children. Processing 3 leaves queue [9,20].
After collecting the level, reverse it only when the flag is right to left. On the second level, [9,20] becomes [20,9].
Append the completed level and flip the flag exactly once. The remaining queue [15,7] becomes the next left-to-right level.
Stop when the queue is empty and return [[3],[20,9],[15,7]] in Example 1.

Why It Works

Initially the queue holds exactly depth 0. At each iteration the saved size freezes the current depth; processing those nodes and adding left children before right children creates the next depth in left-to-right order. Every node has one parent, so it is queued exactly once. Reversing an odd-depth list changes precisely its display order, while even-depth lists stay unchanged. Children remain in their normal queue order regardless of the display direction. The flag starts true and flips once per completed depth, giving exactly the required alternating directions. No tree field is assigned.

Dry Run

BFS Then Reverse: variable states at each step
Event	Size / i	Direction	Logical queue after event	Current level	Completed result
initialize	not saved	left to right	[3]	[]	[]
process 3; enqueue 9,20	1 / 0	left to right	[9,20]	[3]	[]
append; flip	1 / complete	right to left next	[9,20]	[3]	[[3]]
process 9	2 / 0	right to left	[20]	[9]	[[3]]
process 20; enqueue 15,7	2 / 1	right to left	[15,7]	[9,20]	[[3]]
reverse then append; flip	2 / complete	left to right next	[15,7]	[20,9]	[[3],[20,9]]
process 15	2 / 0	left to right	[7]	[15]	[[3],[20,9]]
process 7	2 / 1	left to right	[]	[15,7]	[[3],[20,9]]
append; flip; return	2 / complete	right to left next	[]	[15,7]	[[3],[20,9],[15,7]]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

For n nodes and maximum level width w, each node is queued and processed once. Reversals touch at most n values altogether, so they do not change the linear bound. Java ArrayDeque and Python deque provide constant amortized queue operations. JavaScript compacts only once per level, copying each next-frontier reference once overall. Auxiliary queue and current-level storage use O(w), worst-case O(n); output stores n values and one independent list per depth, O(n), so total allocation is O(n). All traversal is iterative, including a depth-2000 chain.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.ArrayList;3import java.util.List;4import java.util.Queue;5
6class TreeNode {7    int val;8    TreeNode left, right;9    TreeNode(int val) { this.val = val; }10}11
12class Solution {13    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {14        List<List<Integer>> result = new ArrayList<>();15        if (root == null) return result;16        Queue<TreeNode> queue = new ArrayDeque<>();17        queue.offer(root);18        boolean leftToRight = true;19        while (!queue.isEmpty()) {20            // Freeze the boundary before enqueuing children from the next depth.21            int levelSize = queue.size();22            List<Integer> level = new ArrayList<>(levelSize);23            for (int i = 0; i < levelSize; i++) {24                TreeNode node = queue.poll();25                level.add(node.val);26                if (node.left != null) queue.offer(node.left);27                if (node.right != null) queue.offer(node.right);28            }29            if (!leftToRight) java.util.Collections.reverse(level);30            result.add(level);31            leftToRight = !leftToRight;32        }33        return result;34    }35}

Hints

Hint 1

Discover one complete depth at a time with a saved queue size.

Hint 2

Alternate only the output order; enqueue left then right children on every level.

Hint 3

For a level of size k, reverse position i by writing at k - 1 - i.

Edge Cases

An empty tree returns [], and a singleton returns [[value]].
A 2000-node chain has a singleton on every level, so reversing changes nothing; iterative BFS avoids stack depth limits.
Missing children are skipped, not output as null; Example 4 still preserves left-to-right discovery for the third level.
Duplicate and negative values are separate occurrences; direction depends on depth, not on values.
A broad tree maximizes queue width; every output level must own a distinct mutable list.

Common Mistakes and Interview Tips

Reversing child enqueue order along with the output changes the next level incorrectly.
Reading the live queue size during the inner loop lets newly added children enter the current level.
Using shift() or unshift() per value in JavaScript, or Python pop(0), repeatedly copies wide arrays and can become quadratic.
Using k - i instead of k - 1 - i writes outside the level.
Flipping direction per node instead of per level produces mixed output.
Both approaches are O(n); direct indexing removes a pass, not an asymptotic factor. Keep results local and allocate a fresh list per level.

Key Takeaway

Level-order problems are breadth-first searches with per-level bookkeeping, so a small flag or index tweak adapts the same traversal to zigzag orders, averages, and side views.