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 where the direction alternates on every level. The first level is left-to-right, the next right-to-left, then left-to-right again, forming a zigzag pattern.
Approach 1: Breadth-First Search with Direction Toggle (O(n) time, O(n) space)
This approach performs a standard Breadth-First Search using a queue to process the tree level by level. For each level, collect node values in an array. Maintain a boolean flag that tracks traversal direction. When the flag indicates right-to-left, reverse the collected level values before adding them to the result (or insert at the front while building the level). Every node is visited exactly once, so the time complexity is O(n), and the queue plus result storage requires O(n) space.
The key insight is that zigzag order does not require changing the traversal itself. The queue still processes nodes left-to-right. Only the way values are stored for each level changes. This makes the implementation simple and reliable for any Tree or Binary Tree level traversal problem.
Approach 2: Depth-First Search with Depth Registration (O(n) time, O(n) space)
This approach uses recursive DFS while tracking the current depth. Maintain a list of lists where each index represents a level. When visiting a node, check the depth: if the level does not exist yet, create a new list. For even depths, append the value normally; for odd depths, insert the value at the beginning of the list. This produces the zigzag order during traversal without reversing later.
DFS explores nodes using recursion but still ensures every node is processed exactly once. The recursion stack can grow up to the tree height, giving O(h) stack usage, while the result structure stores all nodes for O(n) total space.
Recommended for interviews: The BFS solution is the most common and expected answer. Interviewers want to see that you recognize this as a level-order traversal problem and apply a direction toggle. DFS with depth tracking shows deeper understanding of tree traversal patterns, but BFS is typically clearer and easier to implement under interview time constraints.
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.
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.
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.
To implement zigzag level order traversal, we need to add a flag left on the basis of level order traversal. This flag is used to mark the order of the node values in the current level. If left is true, the node values of the current level are stored in the result array ans from left to right. If left is false, the node values of the current level are stored in the result array ans from right to left.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search with Direction Toggle | O(n) | O(n) | Best general solution for level-order traversal problems and the most common interview answer |
| Depth-First Search with Depth Registration | O(n) | O(n) | Useful when you prefer recursion or want to build levels during DFS traversal |
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python • NeetCodeIO • 29,392 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