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 <= 100The key idea in Binary Tree Zigzag Level Order Traversal is to perform a level-by-level traversal while alternating the direction of reading nodes at each level. A common strategy is to use Breadth-First Search (BFS) with a queue. Process nodes level by level, and keep track of the current traversal direction. For one level, append node values from left to right; for the next level, reverse the order or insert values from right to left.
To efficiently manage direction changes, you can either reverse the level result after traversal or use a structure like a deque to insert values at the front or back depending on the current direction. After finishing each level, toggle the traversal direction before moving to the next level.
This approach ensures every node is processed exactly once. The overall time complexity is O(n), where n is the number of nodes, and the space complexity is O(n) due to the queue used for level-order traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS with Queue (Level Order + Direction Toggle) | O(n) | O(n) |
| BFS with Deque for Zigzag Insertion | O(n) | O(n) |
take U forward
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Definition for a binary tree node.
5typedef struct TreeNode {
6
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it can also be solved using Depth-First Search by tracking the current level during recursion. Values are added to a list corresponding to the level, and depending on whether the level is even or odd, values are appended or inserted at the beginning.
Yes, this problem is a common tree traversal question frequently asked in technical interviews at FAANG and other top tech companies. It tests understanding of BFS, tree traversal patterns, and handling level-based logic.
A queue is commonly used to perform level-order traversal of the binary tree. Additionally, a deque can be helpful for inserting values at both ends depending on the traversal direction. This allows efficient zigzag ordering without extra reversing.
The optimal approach uses Breadth-First Search (BFS) with a queue to traverse the tree level by level. A boolean flag or level index is used to alternate the direction of traversal, creating the zigzag pattern. This ensures every node is processed once with O(n) time complexity.
This JavaScript DFS implementation recursively manipulates a result array, inserting at either the start or end of each level array according to current depth parity. Recursive calls facilitate the traversal.