Zig Zag or Spiral Traversal
MediumLevel order, reversing alternate rows
Problem
Return the zig-zag level order of a binary tree (alternating left-right and right-left per level).
Do a level-order walk but flip the direction of every other row.
The idea
Traverse level by level as normal and flip a flag each level, reversing the collected row before appending. Collecting then reversing is far simpler than trying to enqueue in alternating directions.
The trick
- Reverse the finished level, do not change the queue order.
- Inserting at the front of a deque avoids the reverse.
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.