Binary Tree Zigzag Level Order Traversal — Solution
Binary Tree Zigzag Level Order Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Binary Tree Zigzag Level Order Traversal is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its node values level by level in zigzag order: the root's level is read from left to right, the next level from right to left, the one after from left to right again, and so on, alternating at every level.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation: Level 1 reads left to right, level 2 right to left (20 before 9), level 3 left to right again.
Example 2
Input: root = [1,2,3,4,null,null,5]
Output: [[1],[3,2],[4,5]]
Explanation: Level 2 is read right to left: 3, 2. Level 3 is read left to right: 4, 5.
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no levels.
Constraints
0 <= number of nodes <= 2000-100 <= Node.val <= 100
Hints for Binary Tree Zigzag Level Order Traversal
Hint 1
Start from an ordinary level-order traversal: one list per level, left to right.
Hint 2
The zigzag only changes the order inside each level, never which nodes are on it.
Hint 3
Keep a flag that flips after every level, and fill each level's list from the front or from the back according to it — the queue itself always runs left to right.
How to solve Binary Tree Zigzag Level Order Traversal
Run a normal breadth-first level traversal and reverse the direction in which every other level's values are written.
Approach
- If the tree is empty, return an empty list.
- Process the tree level by level with a queue, children added left before right.
- For a level of
sizenodes, create a list of that size; the i-th node taken goes to index i on a left-to-right level and to indexsize - 1 - ion a right-to-left one. - Append the list and flip the direction before the next level.
Why it works
The traversal itself never changes, so every level contains exactly its nodes; writing them into mirrored positions on alternate levels produces precisely the right-to-left reading of those levels.
Complexity
- Time —
O(n) - Space —
O(w), w the largest number of nodes on one level (plus the output)
Pitfalls
- Do not try to reverse the order children are enqueued — that scrambles the next level instead of reversing this one.
- The first level (the root) is read left to right.
Reference solution
Python
from typing import List, Optional
def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
out = []
level = [root] if root else []
left_to_right = True
while level:
row = [node.val for node in level]
if not left_to_right:
row.reverse()
out.append(row)
left_to_right = not left_to_right
nxt = []
for node in level:
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
level = nxt
return outJava
public static int[][] zigzagLevelOrder(TreeNode root) {
List<int[]> out = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.add(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
int[] row = new int[size];
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
row[leftToRight ? i : size - 1 - i] = node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
out.add(row);
leftToRight = !leftToRight;
}
return out.toArray(new int[0][]);
}C++
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> out;
queue<TreeNode*> q;
if (root) q.push(root);
bool leftToRight = true;
while (!q.empty()) {
int size = (int) q.size();
vector<int> row(size);
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
row[leftToRight ? i : size - 1 - i] = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
out.push_back(row);
leftToRight = !leftToRight;
}
return out;
}JavaScript
var zigzagLevelOrder = function(root) {
var out = [];
if (root === null) return out;
var queue = [root], head = 0, leftToRight = true;
while (head < queue.length) {
var end = queue.length, size = end - head, row = new Array(size);
for (var i = 0; i < size; i++) {
var node = queue[head++];
row[leftToRight ? i : size - 1 - i] = node.val;
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
out.push(row);
leftToRight = !leftToRight;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 156 breadth-first search problems · the whole catalogue
Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals