Zigzag Level Order
MediumLevel order, reversing every other row
Problem
Return the level-order traversal of a binary tree, but alternate the direction each level (left-to-right, then right-to-left).
Do a level-order walk but flip the direction of every other row.
The idea
Traverse level by level exactly as normal and flip a boolean each level, reversing that level's list before appending it. Reversing the collected row is far simpler than trying to traverse in alternating directions.
The trick
- Collect the level normally, then reverse — do not fight the queue.
- Inserting at the front of a deque avoids the O(n) reverse if you care.
Step 1 of 5. Level-order BFS: snapshot the queue size to process exactly one level per iteration.
Fix the level width up front.
1const q = [root], out = [];2while (q.length) {3 const level = [];4 for (let n = q.length; n > 0; n--) {5 const node = q.shift();6 level.push(node.val);7 if (node.left) q.push(node.left);8 if (node.right) q.push(node.right);9 }10 out.push(level);11}Input
- nodes
- 6, 5 edges
Memory
- levels
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,9,20,null,null,15,7]
- Output:
- [[3], [20, 9], [15, 7]]
- Explanation:
- Levels alternate left-to-right and right-to-left.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [[1], [3, 2]]
- Explanation:
- Row 2 reverses to 3,2.
Example 3
- Input:
- tree = [1]
- Output:
- [[1]]
- Explanation:
- One level.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.