On this page

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 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Expected 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

  1. Run the usual BFS with a queue, one level at a time (snapshot the queue size).
  2. Keep a boolean leftToRight, starting as true.
  3. For each level, create an array level of that size.
  4. For the i-th node popped, write its value at index i if leftToRight, otherwise at index size - 1 - i.
  5. Push the children left then right as usual.
  6. 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