Binary Tree Zigzag Level Order Traversal
Given the root of a binary tree, return the zigzag level order traversal: the first level left to right, the next level right to left, then left to right again, alternating.
Constraints:
- The number of nodes is in the range
[0, 2000]. -100 <= Node.val <= 100
Intuition
1 12 / \3 2 34 / \ \5 4 5 6Expected output: [[1], [3, 2], [4, 5, 6]].
This is the normal level order traversal with one change: every second level is written in reverse. The queue still processes nodes left to right. Only where each value is written inside the level changes.
Approach: BFS with a Direction Flag
- Run the usual BFS with a queue, one level at a time (snapshot the queue size).
- Keep a boolean
leftToRight, starting as true. - For each level, create an array
levelof that size. - For the i-th node popped, write its value at index
iifleftToRight, otherwise at indexsize - 1 - i. - Push the children left then right as usual.
- After the level, flip the flag.
Filling by index means we never need to reverse the array afterwards.
Code
class Solution {public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans;if (root == nullptr) return ans;queue<TreeNode*> q;q.push(root);bool leftToRight = true;while (!q.empty()) {int size = q.size();vector<int> level(size);for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();int index = leftToRight ? i : size - 1 - i;level[index] = node->val;if (node->left != nullptr) q.push(node->left);if (node->right != nullptr) q.push(node->right);}ans.push_back(level);leftToRight = !leftToRight;}return ans;}};
Complexity
Time: O(n)
Each node enters and leaves the queue once, and each value is written to its slot once.
Space: O(w)
The queue and the current level array hold at most one level, where w is the maximum width.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"Zigzag is a normal level order traversal where every second level is reversed. I run the usual BFS with a queue and the size snapshot per level. I keep a left to right flag. For each level I allocate an array of that size, and for the i-th node I write its value at index i when the flag is true, or at size minus one minus i when it is false. That way I never reverse the array afterwards. I always push the left child then the right child, and I flip the flag after each level. Time is O of n and space is O of the maximum width."
Next TopicBoundary Traversal