Binary Tree Zigzag Level Order Traversal - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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.
Approach 1: Breadth-First Search with Direction Toggle
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.
Complexity
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.
Approach 2: Depth-First Search with Depth Registration
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.
Complexity
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 3: BFS
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.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python • NeetCodeIO • 30,794 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Tree Zigzag Level Order Traversal easy or hard?
How to solve Binary Tree Zigzag Level Order Traversal in O(n)?
Binary Tree Zigzag Level Order Traversal Python or Java solution?
What is the best approach for Binary Tree Zigzag Level Order Traversal?
What data structure is used in Binary Tree Zigzag Level Order Traversal?
What is the time complexity of Binary Tree Zigzag Level Order Traversal?
Is Binary Tree Zigzag Level Order Traversal asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Binary Tree Zigzag Level Order Traversal with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor