Watch 10 video solutions for Binary Tree Zigzag Level Order Traversal, a medium level problem involving Tree, Breadth-First Search, Binary Tree. This walkthrough by take U forward has 299,751 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |