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:
[0, 2000].-100 <= Node.val <= 100Problem Overview: Given the root of a binary tree, return the level order traversal of its nodes but alternate the direction at each level. The first level is left-to-right, the next level is right-to-left, and the pattern continues in a zigzag manner.
Approach 1: Breadth-First Search with Direction Toggle (Time: O(n), Space: O(n))
This approach performs a standard level-order traversal using a queue, which is the natural technique for Breadth-First Search. Process nodes level by level by tracking the current queue size. For each level, collect values in a temporary list. A boolean flag (leftToRight) determines insertion order. If the direction is normal, append values directly. If reversed, insert values at the front or reverse the list after the level finishes.
The key insight is that zigzag order does not require modifying traversal order. The tree is still processed level-by-level exactly like a typical BFS. Only the output order changes. After processing a level, flip the direction flag before moving to the next level. This keeps the implementation clean and avoids complex pointer manipulation inside the tree structure.
This is the most intuitive solution when working with Binary Tree traversal problems. Queue operations stay constant time and every node is visited once, producing an overall time complexity of O(n) and auxiliary space of O(n) due to the queue and output list.
Approach 2: Depth-First Search with Depth Registration (Time: O(n), Space: O(n))
This approach uses recursive Tree traversal instead of BFS. Maintain a result list where each index represents a depth level. During DFS, when visiting a node, check whether the current depth already has a list. If not, create one. Then insert the node's value according to the level's direction.
If the depth is even, append the value normally. If the depth is odd, insert the value at the front of that level's list. The recursion explores the left and right children while incrementing the depth parameter. Because DFS visits nodes in preorder style but still tracks their depth, it can simulate level grouping without a queue.
This method works well if you prefer recursion or when BFS queues are inconvenient in the language you are using. Each node is processed exactly once, giving O(n) time complexity. The recursion stack plus output storage requires O(n) space in the worst case for skewed trees.
Recommended for interviews: Breadth-First Search with a direction toggle is what most interviewers expect. It mirrors classic level-order traversal and clearly demonstrates queue-based BFS reasoning. Showing the DFS variant afterward proves you understand how depth tracking can replicate level-order behavior using recursion.
This approach leverages the standard Breadth-First Search (BFS) algorithm to perform a level order traversal. We use a queue to traverse the tree level-by-level. For each level, we determine the order (left-to-right or right-to-left) by toggling a flag. At odd levels, we simply reverse the order of elements collected from the queue to achieve the zigzag effect.
This C solution uses a queue to perform a level order traversal of the tree. It maintains an array of lists, where each list contains values of nodes at the same level. We also keep track of the direction using the level number: odd levels are reversed using an auxiliary reverse function. This solution balances both clarity and efficiency.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(n), for storing the output and additional structures, like the queue used for BFS.
In contrast to the BFS method, this approach utilizes Depth-First Search (DFS) for traversal. Recursive calls are made to process each node, and a hashmap (or similar structure) tracks the current depth. Depending on the depth, nodes are appended to the left or right of the current level list. This achieves the zigzag pattern as the recursion progresses.
The C solution uses DFS and depth-tracking to achieve the zigzag pattern. It employs memory allocation based on anticipated maximum operations across the tree's potential levels. Level reversals on odd levels are managed via element insertion shifts within depth-correlated arrays.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as DFS visits each node once.
Space Complexity: O(n), considering both storage needs for recursive calls and the result list.
| Approach | Complexity |
|---|---|
| Breadth-First Search with Direction Toggle | Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed once. |
| Depth-First Search with Depth Registration | Time Complexity: O(n), as DFS visits each node once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search with Direction Toggle | O(n) | O(n) | Best for level-order traversal problems and the most common interview solution |
| Depth-First Search with Depth Registration | O(n) | O(n) | Useful when recursion is preferred or when tracking depth during DFS traversal |
L19. Zig-Zag or Spiral Traversal in Binary Tree | C++ | Java • take U forward • 299,751 views views
Watch 9 more video solutions →Practice Binary Tree Zigzag Level Order Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor