Binary Tree Zigzag Level Order Traversal
Asked at Oracle, Walmart
Problem
Given a binary tree, return the zigzag level order traversal of its nodes' values. That is, traverse from left to right for the first level, then right to left for the second, and so on. This is a standard BFS variation that tests your ability to alternate traversal direction.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: do a normal BFS level order traversal, then reverse every other level. That's O(n) time and O(n) space — same as regular BFS. The reversal step is O(level_width) per level.
Key insight: use BFS but track the current direction. At each level, collect nodes in order. If the level should be right-to-left, either reverse the list or insert at the front of a deque.
Visual walkthrough for a tree with values [3,9,20,null,null,15,7]:
Level 0: [3] (left to right)
Level 1: [20, 9] (right to left — reversed from [9, 20])
Level 2: [15, 7] (left to right)
Result: [[3],[20,9],[15,7]]
Alternative approach without reversing: use a deque. For left-to-right levels, pop from the front and push children to the back (left then right). For right-to-left levels, pop from the back and push children to the front (right then left). This avoids the O(level_width) reversal.
The direction flag toggles each level. Start with left-to-right (direction = 0). After processing each level, flip: direction ^= 1. Or track a boolean leftToRight and negate it each level.
Edge cases: empty tree (return empty list), single node (return [[val]]), skewed tree (each level has one node, zigzag is the same as normal traversal).
Optimal Approach
Use BFS with a queue. Track the current level and whether to reverse.
- Initialize queue with root. Set
leftToRight = true. - While queue is not empty:
- Get the current level size.
- For each node in the level, dequeue and collect its value.
- Enqueue left child, then right child.
- After the level, if
leftToRightis false, reverse the collected values. - Toggle
leftToRight.
- Return the result.
Time: O(n) — each node visited once. Reversal is O(level_width), which sums to O(n) across all levels. Space: O(n) — queue holds at most one level of nodes.
What Trips People Up in Real Interviews
Reversing the entire result instead of alternating levels. Only reverse every other level, not the whole result. Level 0 is left-to-right, level 1 is right-to-left, and so on.
Using a vector and calling reverse() on odd levels. This works but is O(level_width) per reversal. Using a deque and push_front is cleaner and avoids the reversal step entirely.
Forgetting that the zigzag pattern applies to the VALUE order, not the node traversal order. You always enqueue left child first, then right. The zigzag only affects how you collect values.
Mixing up the direction at level 0. The first level (root) is left-to-right. Start with leftToRight = true and toggle AFTER processing each level.
Not handling null children. Skip null children when enqueueing — only add non-null children to the queue. Otherwise, you get null pointer exceptions or null values in the result.
Solution Code
from collections import deque
def zigzagLevelOrder(root):
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not left_to_right:
level.reverse()
result.append(level)
left_to_right = not left_to_right
return resultFrequently Asked Questions
What is the Binary Tree Zigzag Level Order Traversal problem?
Given a binary tree, return the zigzag level order traversal of its nodes' values. That is, traverse from left to right for the first level, then right to left for the second, and so on. This is a standard BFS variation that tests your ability to alternate traversal direction.
How do you solve Binary Tree Zigzag Level Order Traversal?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Binary Tree Zigzag Level Order Traversal?
Binary Tree Zigzag Level Order Traversal is asked at Oracle, Walmart. It is a medium difficulty problem.
What are common mistakes on Binary Tree Zigzag Level Order Traversal?
- Reversing the entire result instead of alternating levels. Only reverse every other level, not the whole result. Level 0 is left-to-right, level 1 is right-to-left, and so on.
- Using a `vector` and calling `reverse()` on odd levels. This works but is `O(level_width)` per reversal. Using a `deque` and `push_front` is cleaner and avoids the reversal step entirely.
- Forgetting that the zigzag pattern applies to the VALUE order, not the node traversal order. You always enqueue left child first, then right. The zigzag only affects how you collect values.
- Mixing up the direction at level 0. The first level (root) is left-to-right. Start with `leftToRight = true` and toggle AFTER processing each level.
- Not handling null children. Skip null children when enqueueing — only add non-null children to the queue. Otherwise, you get null pointer exceptions or null values in the result.