Binary Tree Zigzag Level Order Traversal
MedPrompt
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:
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach builds upon the standard BFS level-order traversal. We traverse the tree level by level using a queue. For each level, we store the node values in a temporary list. A flag or a level counter is used to determine the traversal direction. If the current level needs to be traversed from right to left, we simply reverse the temporary list before adding it to our final result.
Algorithm
- Initialize an empty list
resultto store the final zigzag traversal. - If the
rootis null, return the emptyresult. - Initialize a queue (e.g.,
LinkedList) and add therootto it. - Initialize a boolean flag
leftToRighttotrue. - While the queue is not empty:
- Get the number of nodes in the current level,
levelSize. - Create a new list
currentLevelto store the values for this level. - Loop
levelSizetimes:- Dequeue a node.
- Add its value to
currentLevel. - Enqueue its left child if it's not null.
- Enqueue its right child if it's not null.
- If
leftToRightisfalse, reverse thecurrentLevellist. - Add
currentLevelto theresultlist. - Flip the
leftToRightflag for the next level.
- Get the number of nodes in the current level,
- Return the
result.
Walkthrough
This method is a direct extension of the standard Breadth-First Search (BFS) algorithm for level-order traversal. The main idea is to perform a regular level-order traversal and collect all nodes at a given level. After a level is fully processed, we decide whether to add it to the result as is (for left-to-right levels) or to reverse it first (for right-to-left levels). A boolean flag, toggled at the end of each level's processing, keeps track of the required order.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(levelSize); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevel.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } if (!leftToRight) { Collections.reverse(currentLevel); } result.add(currentLevel); leftToRight = !leftToRight; } return result; }}Complexity
Time
O(N)
Space
O(W)
Trade-offs
Pros
Easy to understand as it's a small modification of the standard level-order traversal.
The logic is straightforward and simple to implement.
Cons
The explicit reversal step (
Collections.reverse) adds a performance overhead compared to more optimized solutions, as it requires an extra pass over the nodes of every other level.
This approach uses recursion (DFS) to traverse the tree. We maintain the current level's depth as we traverse. The core idea is to add nodes to the correct level's list in the final result. For even-numbered levels (0, 2, ...), we append the node's value to the end of the list. For odd-numbered levels (1, 3, ...), we insert the node's value at the beginning of the list. This prepending action effectively reverses the order of nodes for odd levels.
Algorithm
- Initialize an empty list
result. - Define a recursive helper function,
dfs(node, level, result). - Call the helper function with the
rootandlevel = 0. - Inside
dfs(node, level, result):- If
nodeis null, return. - If
levelis equal to the current size ofresult, it means we are visiting this level for the first time. Add a newLinkedListtoresult. - Get the list for the current level:
levelList = result.get(level). - If
levelis even, addnode.valto the end oflevelList. - If
levelis odd, addnode.valto the beginning oflevelList. - Recursively call
dfs(node.left, level + 1, result). - Recursively call
dfs(node.right, level + 1, result).
- If
- Return the
result.
Walkthrough
Instead of the iterative BFS, we can solve this problem using a recursive Depth-First Search. We perform a preorder traversal and pass the current depth or level as an argument to the recursive function. The result list will store lists of nodes for each level. When we visit a node at a certain level, we check if a list for this level already exists in our result. If not, we create one. To achieve the zigzag effect, we check if the current level is even or odd. For even levels, we append the node's value to the end of the list. For odd levels, we prepend the value to the beginning of the list. Using a LinkedList for each level's list makes the prepending operation efficient (O(1)).
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); dfs(root, 0, result); return result; } private void dfs(TreeNode node, int level, List<List<Integer>> result) { if (node == null) { return; } // If we are at a new level, create a new list for it. // Using LinkedList for efficient prepending (addFirst). if (level >= result.size()) { result.add(new LinkedList<>()); } List<Integer> levelList = result.get(level); if (level % 2 == 0) { // Left to right levelList.add(node.val); } else { // Right to left // Add at the beginning for odd levels ((LinkedList<Integer>) levelList).addFirst(node.val); } dfs(node.left, level + 1, result); dfs(node.right, level + 1, result); }}Complexity
Time
O(N)
Space
O(H)
Trade-offs
Pros
Elegant recursive solution.
Can be more space-efficient than BFS for balanced trees (O(log N) vs O(N) for queue space).
Cons
Less intuitive for a level-order problem, which is naturally solved with BFS.
Can lead to a
StackOverflowErrorfor very deep, unbalanced trees.Requires using a
LinkedListfor each level to maintain O(1) insertion at the beginning; using anArrayListwould degrade performance.
This is a highly efficient and elegant approach that uses a single double-ended queue (deque). Instead of reversing lists, we control the order of processing nodes and adding their children to the deque. We use a flag to alternate between left-to-right and right-to-left traversal for each level.
Algorithm
- Initialize an empty list
resultand a deque (e.g.,LinkedList). - If
rootis null, return the emptyresult. - Add the
rootto the deque. - Initialize a boolean flag
leftToRighttotrue. - While the deque is not empty:
- Get the number of nodes in the current level,
levelSize. - Create a new list
currentLevelto store values. - Loop
levelSizetimes:- If
leftToRightistrue:- Poll a node from the front of the deque (
pollFirst). - Add its value to
currentLevel. - Add its left child (if not null) to the back of the deque (
offerLast). - Add its right child (if not null) to the back of the deque (
offerLast).
- Poll a node from the front of the deque (
- If
leftToRightisfalse:- Poll a node from the back of the deque (
pollLast). - Add its value to
currentLevel. - Add its right child (if not null) to the front of the deque (
offerFirst). - Add its left child (if not null) to the front of the deque (
offerFirst).
- Poll a node from the back of the deque (
- If
- Add
currentLevelto theresult. - Flip the
leftToRightflag.
- Get the number of nodes in the current level,
- Return
result.
Walkthrough
This optimized BFS approach uses a double-ended queue (deque) to avoid the costly list reversal step. The key is to alter how we process nodes and enqueue their children based on the traversal direction of the current level.
- For a left-to-right level, we poll nodes from the front of the deque and add their children (left then right) to the back.
- For a right-to-left level, we poll nodes from the back of the deque and add their children (right then left) to the front.
This way, the nodes for the next level are always placed in the deque in the correct order for their subsequent traversal, eliminating the need for any post-processing like reversal.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */import java.util.Deque; class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Deque<TreeNode> deque = new LinkedList<>(); deque.offerFirst(root); boolean leftToRight = true; while (!deque.isEmpty()) { int levelSize = deque.size(); List<Integer> currentLevel = new ArrayList<>(levelSize); for (int i = 0; i < levelSize; i++) { if (leftToRight) { TreeNode node = deque.pollFirst(); currentLevel.add(node.val); if (node.left != null) { deque.offerLast(node.left); } if (node.right != null) { deque.offerLast(node.right); } } else { TreeNode node = deque.pollLast(); currentLevel.add(node.val); if (node.right != null) { deque.offerFirst(node.right); } if (node.left != null) { deque.offerFirst(node.left); } } } result.add(currentLevel); leftToRight = !leftToRight; } return result; }}Complexity
Time
O(N)
Space
O(W)
Trade-offs
Pros
Most efficient approach in terms of constant factors as it avoids explicit list reversal.
The logic of adding/removing from both ends of the deque is clean and directly builds the zigzag order.
Uses a single data structure to manage the traversal.
Cons
The logic can be slightly more complex to grasp initially compared to the simple reversal method.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); boolean left = true ; while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); t . add ( node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } if (! left ) { Collections . reverse ( t ); } ans . add ( t ); left = ! left ; } return ans ; } } ////// public class Binary_Tree_Zigzag_Level_Order_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // count as level marker class Solution { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> result = new ArrayList <>(); if ( root == null ) { return result ; } boolean isLeftToRight = true ; Queue < TreeNode > q = new LinkedList <>(); q . offer ( root ); int currentLevelCount = 1 ; int nextLevelCount = 0 ; List < Integer > one = new ArrayList <>(); while (! q . isEmpty ()) { TreeNode current = q . poll (); currentLevelCount --; if ( isLeftToRight ) { one . add ( current . val ); } else { one . add ( 0 , current . val ); } if ( current . left != null ) { q . offer ( current . left ); nextLevelCount ++; } if ( current . right != null ) { q . offer ( current . right ); nextLevelCount ++; } if ( currentLevelCount == 0 ) { currentLevelCount = nextLevelCount ; nextLevelCount = 0 ; result . add ( one ); one = new ArrayList <>(); isLeftToRight = ! isLeftToRight ; } } return result ; } } public class Solution_nullAsMarker { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> list = new ArrayList < List < Integer >>(); if ( root == null ) { return list ; } Queue < TreeNode > q = new LinkedList <>(); q . offer ( root ); q . offer ( null ); // @note: use null as marker for end of level boolean direction = true ; // true: left=>right, false: right=>left List < Integer > oneLevel = new ArrayList <>(); while (! q . isEmpty ()) { TreeNode current = q . poll (); if ( current == null ) { List < Integer > copy = new ArrayList <>( oneLevel ); list . add ( copy ); // clean after one level recorded oneLevel . clear (); // @memorize: this api direction = ! direction ; // @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping // sk.offer(null); // add marker if (! q . isEmpty ()) { q . offer ( null ); // add marker } continue ; } if ( direction ) { oneLevel . add ( current . val ); } else { oneLevel . add ( 0 , current . val ); } // @note:@memorize: since using null as marker, then must avoid adding null when children are null // sk.offer(current.left); // sk.offer(current.right); if ( current . left != null ) { q . offer ( current . left ); } if ( current . right != null ) { q . offer ( current . right ); } } return list ; } } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[][]} */ var zigzagLevelOrder = function (root) { const ans = []; if (!root) { return ans; } const q = [root]; let left = 1; while (q.length) { const t = []; for (let n = q.length; n; --n) { const node = q.shift(); t.push(node.val); if (node.left) { q.push(node.left); } if (node.right) { q.push(node.right); } } if (!left) { t.reverse(); } ans.push(t); left ^= 1; } return ans; };/** * 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 ) { vector < vector < int >> ans ; if ( ! root ) return ans ; queue < TreeNode *> q { { root } }; int left = 1 ; while ( ! q . empty ()) { vector < int > t ; for ( int n = q . size (); n ; -- n ) { auto node = q . front (); q . pop (); t . emplace_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } if ( ! left ) reverse ( t . begin (), t . end ()); ans . emplace_back ( t ); left ^= 1 ; } return ans ; } };# 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 ''' can also use list.insert() >>> my_list = [2, 3, 4] >>> my_list.insert(0, 1) # Insert 1 at the head of the list >>> print(my_list) # Output: [1, 2, 3, 4] >>> a = deque([]) >>> a deque([]) >>> a.append(1) >>> a.append(2) >>> a.append(3) >>> a deque([1, 2, 3]) >>> >>> a.append(0, 555) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: deque.append() takes exactly one argument (2 given) >>> a.insert(0, 555) >>> a deque([555, 1, 2, 3]) ''' from collections import deque class Solution : def zigzagLevelOrder ( self , root : Optional [ TreeNode ]) -> List [ List [ int ]]: ans = [] if root is None : return ans q = deque ([ root ]) ans = [] left = True while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t if left else t [:: - 1 ]) left = ( not left ) return ans ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Solution ( object ): def zigzagLevelOrder ( self , root ): """ :type root: TreeNode :rtype: List[List[int]] """ stack = deque ([ root ]) ans = [] odd = True while stack : level = [] for k in range ( 0 , len ( stack )): top = stack . popleft () if top is None : continue level . append ( top . val ) stack . append ( top . left ) stack . append ( top . right ) if level : if odd : ans . append ( level ) else : ans . append ( level [:: - 1 ]) odd = not odd return ans ############ # 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 ]]: ans = [] if root is None : return ans q = deque ([ root ]) ans = [] left = 1 while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t if left else t [:: - 1 ]) left ^= 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.