Binary Tree Zigzag Level Order Traversal
Medium · Trees · Explanation and code example
Iterative DFS
How it works
This approach converts the recursive DFS to an iterative version using an explicit stack. Each stack entry stores both the node and its depth. We process nodes in the same order as recursive DFS by pushing the right child before the left child (so left is processed first). After collecting all values, we reverse the odd levels.
Steps
- If the root is
null, return an empty list. - Initialize a stack with the root node and depth
0. - While the stack is not empty:
- Pop a node and its depth.
- If this depth is new, create a new list for it.
- Append the node's value to the list at this depth.
- Push the right child (if exists) with
depth + 1. - Push the left child (if exists) with
depth + 1.
- Reverse all lists at odd indices.
- Return the result list.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Reversing Children Order Instead of Values
A common mistake is trying to alternate the order of adding children to the queue (right-then-left vs left-then-right). This does not produce the correct zigzag pattern because it affects future levels, not just the current one.
Off-by-One Error in Level Index Check
Confusing whether level 0 should be left-to-right or right-to-left. The problem defines level 0 (root level) as left-to-right, so odd-indexed levels should be reversed.
Using Deque Operations Incorrectly for Zigzag
Some attempt to use appendleft and append alternately to avoid reversing, but this approach requires careful handling to avoid mixing up the traversal order with the output order, often leading to subtle bugs.
Python code example
from typing import List, Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
stack = [(root, 0)]
while stack:
node, depth = stack.pop()
if depth == len(res):
res.append([])
res[depth].append(node.val)
if node.right:
stack.append((node.right, depth + 1))
if node.left:
stack.append((node.left, depth + 1))
for i in range(len(res)):
if i % 2 == 1:
res[i].reverse()
return res
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
stack<pair<TreeNode*, int>> s;
s.push({root, 0});
while (!s.empty()) {
auto [node, depth] = s.top();
s.pop();
if (depth == res.size()) {
res.push_back({});
}
res[depth].push_back(node->val);
if (node->right) s.push({node->right, depth + 1});
if (node->left) s.push({node->left, depth + 1});
}
for (int i = 0; i < res.size(); i++) {
if (i % 2 == 1) {
reverse(res[i].begin(), res[i].end());
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.