63. Binary Tree Zigzag Level Order Traversal
mediumAsked at WorkdayReturn the zigzag (alternating left-to-right then right-to-left) traversal of a binary tree. Workday uses this to test BFS + per-level transformation — same pattern as alternating row directions when emitting a multi-level approval-chain report.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Workday loops.
- Glassdoor (2025)— Workday SDE2 phone screen.
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).
Constraints
The number of nodes in the tree is in the range [0, 2000].-100 <= Node.val <= 100
Examples
Example 1
root = [3,9,20,null,null,15,7][[3],[20,9],[15,7]]Example 2
root = [1][[1]]Approaches
1. BFS + reverse alternate levels
Standard level-order BFS. Reverse level array on odd levels.
- Time
- O(n)
- Space
- O(n)
// standard BFS, then result.push(leftToRight ? level : level.reverse())Tradeoff: Easy but performs an explicit reverse.
2. BFS with deque-style level build
BFS. For each level, build by pushing front or back based on direction.
- Time
- O(n)
- Space
- O(n)
function zigzagLevelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
let leftToRight = true;
while (queue.length > 0) {
const size = queue.length;
const level = new Array(size);
for (let i = 0; i < size; i++) {
const node = queue.shift();
const idx = leftToRight ? i : size - 1 - i;
level[idx] = node.val;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
leftToRight = !leftToRight;
}
return result;
}Tradeoff: Pre-allocated level array; index from front or back. No explicit reverse.
Workday-specific tips
Workday accepts either reverse-on-odd or pre-allocate-with-index. The pre-allocate version avoids the explicit reverse pass — slightly more efficient and a stronger signal.
Common mistakes
- Forgetting to flip leftToRight after each level.
- Reversing during queue enqueue instead of result building — corrupts BFS order.
- Off-by-one in size - 1 - i for the right-to-left index.
Follow-up questions
An interviewer at Workday may pivot to one of these next:
- Binary Tree Level Order Traversal (LC 102).
- Vertical order traversal (LC 314).
- Boundary of Binary Tree (LC 545).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why pre-allocate?
Avoids the explicit reverse. Same complexity but one fewer O(level-size) pass.
Two stacks?
Alternative: one stack per direction. Pop into the other stack with children in reverse order. Same complexity, more code.