Binary Tree Zigzag Level Order Traversal
Problem
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (i.e., from left to right, then right to left for the next level and alternate between).
- The number of nodes in the tree is in the range [0, 2000]
- −100 ≤ Node.val ≤ 100
Example
root = [3,9,20,null,null,15,7][[3],[20,9],[15,7]]The traversal starts at the root level with value 3, traversed left to right. The next level contains nodes 9 and 20, traversed right to left, so the order is [20, 9]. The final level contains nodes 15 and 7, traversed left to right again, resulting in [15, 7]. The alternating direction at each level creates the zigzag pattern.
Approach
Straightforward Solution
A naive approach performs a standard BFS level order traversal and reverses the list of node values for every alternate level after the traversal. This requires extra passes or additional space to reverse the lists.
Core Observation
A level order traversal naturally processes nodes level by level. The zigzag pattern requires reversing the order of node values at every other level, which can be achieved by controlling the insertion order of node values during traversal.
Path to Optimal
PreviewInstead of reversing after traversal, the algorithm uses a double-ended queue (deque) to insert node values either at the end or the front depending on the current traversal direction…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a BFS queue to traverse the tree level by level. For each level, use a deque to collect node values…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is enqueued and dequeued exactly once during BFS, and each node's value is inserted into the deque once, resulting in linear time proportional to the number of nodes.
Space
O(w) (worst-case O(n))
The BFS queue and the per-level deque each store at most the number of nodes on a single level (the tree's maximum width w). Therefore the auxiliary space is O(w), which is O(n) in the worst case.
Pattern Spotlight
BFS (Level Order Traversal with Direction Toggle)
When a problem requires level order traversal with alternating processing order, integrate direction control into the traversal by using a deque and toggling insertion ends, avoiding costly post-processing reversals.
Solution
| 1 | from collections import deque |
| 2 | |
| 3 | class Solution: |
| 4 | def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: |
| 5 | if not root: |
| 6 | return [] |
| 7 | |
| 8 | res = [] |
| 9 | q = deque([root]) |
| 10 | left_to_right = True |
| 11 | |
| 12 | while q: |
| 13 | level_size = len(q) |
| 14 | level = deque() |
| 15 | |
| 16 | for _ in range(level_size): |
| 17 | node = q.popleft() |
| 18 | |
| 19 | if left_to_right: |
| 20 | level.append(node.val) |
| 21 | else: |
| 22 | level.appendleft(node.val) |
| 23 | |
| 24 | if node.left: |
| 25 | q.append(node.left) |
| 26 | if node.right: |
| 27 | q.append(node.right) |
| 28 | |
| 29 | res.append(list(level)) |
| 30 | left_to_right = not left_to_right |
| 31 | |
| 32 | return res |
Step-by-Step Solution
Handle Empty Tree Edge Case
| 5 | if not root: |
| 6 | return [] |
Objective
To immediately return an empty list if the input tree is empty, as there are no nodes to traverse.
Key Insight
Checking for an empty root node upfront prevents unnecessary setup and traversal logic. This early exit handles the trivial case efficiently and avoids null pointer errors during BFS.
Interview Quick-Check
State & Boundaries
Return [] immediately if root is None, as no traversal is possible.
Initialize BFS Queue and Direction Flag
To set up the initial data structures for BFS traversal and track the current traversal direction.
Traverse Tree Level by Level with Zigzag Ordering
To perform BFS traversal, collecting node values in zigzag order by conditionally appending to the deque based on the current direction.
Return the Zigzag Level Order Result
To return the final list of lists containing node values in zigzag level order after traversal completes.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 1 Critical line interviewers watch for.
level.appendleft(node.val)Insert the node value at the front of the level deque for right-to-left ordering.
This is the core zigzag operation: inserting at the front constructs the reversed order during traversal, avoiding any per-level reversal step afterward.
Full line-by-line criticality + rationale for all 21 lines available on Pro.
Test Your Understanding
Why does using a deque with conditional append or appendleft operations eliminate the need to reverse the level list after traversal?
See the answer with Pro.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Binary Tree Zigzag Level Order Traversal from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Binary Tree Zigzag Level Order Traversal drill