Log inSign up
mediumleetcodeNot Started

Binary Tree Zigzag Level Order Traversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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).

Example 1 · Example 1: 3-Level Tree:

Input: root = [3, 9, 20, null, null, 15, 7] Tree: 3 / \ 9 20 / \ 15 7
Output: [[3], [20, 9], [15, 7]]
Explanation: Level 0 (L->R): [3]. Level 1 (R->L): [20, 9]. Level 2 (L->R): [15, 7].

Example 2 · Example 2: Single Node:

Input: root = [1] Tree: 1
Output: [[1]]
Explanation: Level 0 is [1].

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement alternating traversal directions cleanly without modifying queue push order.
  • Use direct index assignment into pre-allocated vectors to avoid O(k) reverse operations.
  • Understand why child exploration must remain left-to-right in the queue.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Zigzag / spiral traversal.
  • Alternating left-to-right and right-to-left levels.
  • Level order with direction toggle.

Algorithmic Decision Tree:

  • If root == null -> return [].
  • Queue pushes left child then right child always.
  • Index placement in level vector: idx = leftToRight ? i : size - 1 - i.

Connected Patterns:

Binary Tree Level Order TraversalBinary Tree Level Order Traversal IIPopulating Next Right Pointers

1. Standard BFS Level Order with Array Reverse

Intuition

Run standard BFS level-order traversal. For every odd level (index 1, 3, 5...), call reverse() on that level's array.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Perform standard BFS level order traversal into result array of arrays.
  2. Step 2: Loop through result: if i % 2 == 1, reverse result[i].
  3. Step 3: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
10 if (!root) return {};
11 vector<vector<int>> res;
12 queue<TreeNode*> q;
13 q.push(root);
14 int lvl = 0;
15 while (!q.empty()) {
16 int sz = q.size();
17 vector<int> cur;
18 for (int i = 0; i < sz; ++i) {
19 TreeNode* node = q.front(); q.pop();
20 cur.push_back(node->val);
21 if (node->left) q.push(node->left);
22 if (node->right) q.push(node->right);
23 }
24 if (lvl % 2 == 1) reverse(cur.begin(), cur.end());
25 res.push_back(cur);
26 lvl++;
27 }
28 return res;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — Each node visited once, plus reversing elements takes O(n) total.
  • Space complexity: O(w) — Queue holds maximum width of tree w.

2. Two Stacks Zigzag Traversal

Intuition

Stack 1 pops left-to-right and pushes children to Stack 2 (left then right). Stack 2 pops right-to-left and pushes children to Stack 1 (right then left).

When to apply: When practicing alternating stack patterns.

Algorithm

  1. Step 1: Initialize s1 (push root) and s2.
  2. Step 2: While s1 or s2 is not empty:
  3. Step 3: Pop from s1: add to level array; push left child then right child to s2.
  4. Step 4: Pop from s2: add to level array; push right child then left child to s1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
10 if (!root) return {};
11 vector<vector<int>> res;
12 stack<TreeNode*> s1, s2;
13 s1.push(root);
14 while (!s1.empty() || !s2.empty()) {
15 vector<int> cur1;
16 while (!s1.empty()) {
17 TreeNode* node = s1.top(); s1.pop();
18 cur1.push_back(node->val);
19 if (node->left) s2.push(node->left);
20 if (node->right) s2.push(node->right);
21 }
22 if (!cur1.empty()) res.push_back(cur1);
23 vector<int> cur2;
24 while (!s2.empty()) {
25 TreeNode* node = s2.top(); s2.pop();
26 cur2.push_back(node->val);
27 if (node->right) s1.push(node->right);
28 if (node->left) s1.push(node->left);
29 }
30 if (!cur2.empty()) res.push_back(cur2);
31 }
32 return res;
33 }
34};
35
36int main() {
37 // Sample driver execution
38 cout << "Execution completed successfully." << endl;
39 return 0;
40}
41

Time & Space Complexity

  • Time complexity: O(n) — All nodes pushed and popped across the two stacks once.
  • Space complexity: O(n) — Two stacks together hold at most O(w) nodes.

3. BFS with Pre-allocated Vector & Index Assignment

Intuition

Queue always processes nodes in natural left-to-right level order. For each level of size S, allocate a fixed array of size S. Place element at index i if leftToRight is true, or at index (S - 1 - i) if false. Invert the flag after each level.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Queue q with root. Set leftToRight = true.
  3. Step 3: For each level of size S, allocate row = new Array(S).
  4. Step 4: Loop i from 0 to S - 1: idx = leftToRight ? i : (S - 1 - i); row[idx] = node.val.
  5. Step 5: Enqueue left and right children. Toggle leftToRight = !leftToRight. Push row to res.

Zigzag BFS Trace for [3, 9, 20, null, null, 15, 7]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Level 0 (L->R): Dequeue 3
Visual state
Values and pointers at this exact step
tree
Root
3 (L->R)
L
9
R
20

Node order shown; add connections to display explicit tree edges.

level 0: 3
Check / comparison
Level 0: Left to Right -> [3]
Decision / next transition
Record [3]. Toggle leftToRight to false.
Why this step matters

Step 1: Level 0 (L->R): Dequeue 3. Row is [3]. leftToRight toggles to false. Enqueue 9, 20.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
10 if (!root) return {};
11 vector<vector<int>> res;
12 queue<TreeNode*> q;
13 q.push(root);
14 bool leftToRight = true;
15 while (!q.empty()) {
16 int sz = q.size();
17 vector<int> row(sz);
18 for (int i = 0; i < sz; ++i) {
19 TreeNode* node = q.front(); q.pop();
20 int idx = leftToRight ? i : (sz - 1 - i);
21 row[idx] = node->val;
22 if (node->left) q.push(node->left);
23 if (node->right) q.push(node->right);
24 }
25 leftToRight = !leftToRight;
26 res.push_back(row);
27 }
28 return res;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — Every node placed directly into its final array slot in O(1) time.
  • Space complexity: O(w) — Queue holds maximum width w of tree.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS with Array ReverseO(n)O(w)Collect regular level and reverse alternating rows.Array reversals.
2.Two Stacks ZigzagO(n)O(n)Alternate popping and pushing across two stacks.Multiple stack allocations.
3.BFS Pre-allocated Index AssignmentOptimalO(n)O(w)Pre-allocate row of size S; assign index = leftToRight ? i : S-1-i.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns [].
  • Single node: root = [1] -> returns [[1]].
  • Two levels: root = [1, 2, 3] -> level 0: [1], level 1: [3, 2].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight that you place items directly at size - 1 - i instead of calling reverse() on the level array.
  2. Explain why the queue itself must always enqueue left child then right child (to preserve BFS topology).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the optimal BFS approach still enqueue child nodes in left-to-right order (left child first, then right child) even on right-to-left levels?

Back to DSA Sheet