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).
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Approach
- Use a Queue (q) for level-order traversal (BFS).
- Track the current level (level) to know the direction:
- Even levels: Left to Right → use
push(). - Odd levels: Right to Left → use
unshift()to insert at the beginning.
- Even levels: Left to Right → use
- For each level:
- Process all nodes in the current level (
levelSize) - Collect their values in
levelArr. - Add their children to the queue.
- Process all nodes in the current level (
- After processing the level, push
levelArrtoansand increaselevel. - Return the final result array
ans.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h) recursion stack space (h=tree height)
Dry Run
Function Call: zigzagLevelOrder(root) where
root = TreeNode(1)
├── left: TreeNode(2)
│ ├── left: TreeNode(4)
│ └── right: TreeNode(5)
└── right: TreeNode(3)
Step 1:
→ Check if root is null → No
→ Initialize: ans = [], q = [1], level = 0
Step 2 (level = 0):
→ levelSize = 1
→ Initialize levelArr = []
→ i = 0: curr = 1
→ level % 2 == 0 → Push 1 to levelArr → levelArr = [1]
→ Push 2 and 3 to queue → q = [2, 3]
→ Push levelArr to ans → ans = [[1]]
→ Increment level → level = 1
Step 3 (level = 1):
→ levelSize = 2
→ Initialize levelArr = []
→ i = 0: curr = 2
→ level % 2 != 0 → Unshift 2 → levelArr = [2]
→ Push 4 and 5 to queue → q = [3, 4, 5]
→ i = 1: curr = 3
→ level % 2 != 0 → Unshift 3 → levelArr = [3, 2]
→ No children to push
→ Push levelArr to ans → ans = [[1], [3, 2]]
→ Increment level → level = 2
Step 4 (level = 2):
→ levelSize = 2
→ Initialize levelArr = []
→ i = 0: curr = 4
→ level % 2 == 0 → Push 4 → levelArr = [4]
→ No children to push
→ i = 1: curr = 5
→ level % 2 == 0 → Push 5 → levelArr = [4, 5]
→ No children to push
→ q = [] → Queue is empty
→ Push levelArr to ans → ans = [[1], [3, 2], [4, 5]]
Final Result: [[1], [3, 2], [4, 5]]
root = TreeNode(1)
├── left: TreeNode(2)
│ ├── left: TreeNode(4)
│ └── right: TreeNode(5)
└── right: TreeNode(3)
Step 1:
→ Check if root is null → No
→ Initialize: ans = [], q = [1], level = 0
Step 2 (level = 0):
→ levelSize = 1
→ Initialize levelArr = []
→ i = 0: curr = 1
→ level % 2 == 0 → Push 1 to levelArr → levelArr = [1]
→ Push 2 and 3 to queue → q = [2, 3]
→ Push levelArr to ans → ans = [[1]]
→ Increment level → level = 1
Step 3 (level = 1):
→ levelSize = 2
→ Initialize levelArr = []
→ i = 0: curr = 2
→ level % 2 != 0 → Unshift 2 → levelArr = [2]
→ Push 4 and 5 to queue → q = [3, 4, 5]
→ i = 1: curr = 3
→ level % 2 != 0 → Unshift 3 → levelArr = [3, 2]
→ No children to push
→ Push levelArr to ans → ans = [[1], [3, 2]]
→ Increment level → level = 2
Step 4 (level = 2):
→ levelSize = 2
→ Initialize levelArr = []
→ i = 0: curr = 4
→ level % 2 == 0 → Push 4 → levelArr = [4]
→ No children to push
→ i = 1: curr = 5
→ level % 2 == 0 → Push 5 → levelArr = [4, 5]
→ No children to push
→ q = [] → Queue is empty
→ Push levelArr to ans → ans = [[1], [3, 2], [4, 5]]
Final Result: [[1], [3, 2], [4, 5]]
var zigzagLevelOrder = function(root) {
if (!root) return [];
let ans = [];
let q = [root];
let level = 0;
while (q.length) {
let levelArr = [];
let levelSize = q.length;
for (let i = 0; i < levelSize; i++) {
let curr = q.shift();
if (level % 2 === 0) {
levelArr.push(curr.val);
} else {
levelArr.unshift(curr.val);
}
if (curr.left) q.push(curr.left);
if (curr.right) q.push(curr.right);
}
ans.push(levelArr);
level++;
}
return ans;
};
from collections import deque
def zigzagLevelOrder(root):
if not root:
return []
res = []
q = deque([root])
level = 0
while q:
size = len(q)
level_nodes = deque()
for _ in range(size):
node = q.popleft()
if level % 2 == 0:
level_nodes.append(node.val)
else:
level_nodes.appendleft(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(list(level_nodes))
level += 1
return res
public List> zigzagLevelOrder(TreeNode root) {
List> result = new ArrayList<>();
if (root == null) return result;
Queue q = new LinkedList<>();
q.offer(root);
boolean leftToRight = true;
while (!q.isEmpty()) {
int size = q.size();
Integer[] level = new Integer[size];
for (int i = 0; i < size; i++) {
TreeNode curr = q.poll();
int index = leftToRight ? i : size - 1 - i;
level[index] = curr.val;
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
result.add(Arrays.asList(level));
leftToRight = !leftToRight;
}
return result;
}
vector> zigzagLevelOrder(TreeNode* root) {
vector> ans;
if (!root) return ans;
queue q;
q.push(root);
bool leftToRight = true;
while (!q.empty()) {
int size = q.size();
vector level(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front(); q.pop();
int index = leftToRight ? i : size - i - 1;
level[index] = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(level);
leftToRight = !leftToRight;
}
return ans;
}
void zigzagLevelOrder(TreeNode* root) {
if (root == NULL) return;
Queue* q = createQueue();
enqueue(q, root);
int level = 0;
while (!isEmpty(q)) {
int size = queueSize(q);
int* levelArr = new int[size];
for (int i = 0; i < size; i++) {
TreeNode* curr = dequeue(q);
int index = (level % 2 == 0) ? i : size - 1 - i;
levelArr[index] = curr->val;
if (curr->left) enqueue(q, curr->left);
if (curr->right) enqueue(q, curr->right);
}
printArray(levelArr, size);
level++;
}
}
public IList> ZigzagLevelOrder(TreeNode root) {
IList> result = new List>();
if (root == null) return result;
Queue q = new Queue();
q.Enqueue(root);
bool leftToRight = true;
while (q.Count > 0) {
int size = q.Count;
int[] level = new int[size];
for (int i = 0; i < size; i++) {
TreeNode curr = q.Dequeue();
int index = leftToRight ? i : size - i - 1;
level[index] = curr.val;
if (curr.left != null) q.Enqueue(curr.left);
if (curr.right != null) q.Enqueue(curr.right);
}
result.Add(level.ToList());
leftToRight = !leftToRight;
}
return result;
}
