Binary Tree Zigzag Level Order Traversal
Difficulty: Medium
Asked in: Amazon, Microsoft
Understanding the Problem
Given 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
Input: Given binary tree [5,8,2,null,null,6,4]
3
/ \
9 20
/ \
15 7
Output: Return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
The node structure passed to your function will be
class TreeNode
{
int val
TreeNode left
TreeNode right
}
Solutions
 Recursive Depthfirst search approach: Make a DFS search from the root and for even levels reverse the list values at that level.
 Iterative Level Order Traversal approach: Follow an iterative Level order traversal and for each level, poll the visited element from the Queue maintaining a boolean flag to toggle traversals.
You may try to solve this problem here.
1. Recursive DepthFirst Search(DFS) Approach
If you will think about the problem, you will realize that this problem is basically a preorder or postorder traversal with the only difference that for each level, the traversal toggles between left to right and right to left.
However, the problems require to return a twodimensional array that will contain the zigzag traversal of the tree in a level order fashion.
So, We could create a
res
array and make a DFS or preorder tree traversal, while passing another argument called
level
. If the level is even, then we will add the root value in the
array in the end of the
res
otherwise, at the beginning of
res[level]
. To reduce the time complexity of shifting, we can use an array of a doubly linked list and before returning, convert all the doubly linked lists into an array.
res[level]
Example:
Solution step
 Create an array of lists (this will be our output)
 Call recursively DFS function that adds current node value to the output by level.
 In your recursive call, use the level of this node in the tree as an argument.

If it’s even → Insert into the end of the list with
index = level

if it’s odd → Insert into the beginning of list with
index = level
int[][] zigzagLevelOrder(TreeNode root) {
int[][] res
zigzagLevelOrder(root, res, 0)
return res
}
void zigzagLevelOrder(TreeNode root, int[][] res, int level) {
if (root is not null){
if (res.size() <= level)
res.append([])
if (level%2==0)
res[level].append(root.val) // Inserts at the end of the list
else
res[level].insert(0, root.val) // Inserts at the beginning of the list
zigzagLevelOrder(root.left, res, level+1)
zigzagLevelOrder(root.right, res, level+1)
}
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n), the space complexity is the height of the tree , which in worstcase is n.
Critical Ideas to Think
 How did we toggle from left to right and right to left traversal on each level?
 Do you think that this algorithm could also be implemented by using postorder or inorder traversal? How?
 How does the algorithm work if at any level there is only one node available? Check using a sample test case.
2. Iterative Level Order Traversal Approach
Solution steps
 A better idea for ZigZag Level Order Traversal is the BreadthFirst Approach that we use in a Level Order Traversal. Add a root node to Queue.
 Iterate until the contents of the queue become empty.

Reset the
level

A boolean
flag
flag
level

Once a visited node’s value has been added to
level

If the entire level of nodes has been visited, add the level list to the final result list. Toggle
flag
Pseudo Code
int[][] zigzagLevelOrder(TreeNode root) {
int[][] res
if(root is null)
return res
//declare queue
Queue(TreeNode) queue
queue.add(root)
boolean zigzag = false
while( queue is not Empty) {
//declare level list and size from q
int[] level
int size = queue.size()
for (int i = 0 to i < size) {
//poll from q
TreeNode node = queue.pop()
if (zigzag) {
level.add(0, node.val)
} else {
level.add(node.val)
}
if (node.left is not null) {
queue.add(node.left)
}
if (node.right is not null) {
queue.add(node.right)
}
}
res.add(level)
zigzag = !zigzag
}
return res
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
Critical Ideas to Think
 Why we are iterating in the inner for loop till the size of the queue?

What does the statement
zigzag = !zigzag

What is the use of
level
Comparison of Solutions
Suggested Problems to Solve
 Iterative Post Order Binary tree Traversal
 Binary Tree Level Order Traversal
 Binary Tree Spiral Traversal
 Flatten Binary Tree in Level Order Traversal
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!