103. Binary Tree Zigzag Level Order Traversal

Problem Description

The problem requires us to perform a modified level-order traversal on a binary tree. Here, 'zigzag' level order means that the values of nodes at each level of the tree should be traversed and returned in a manner that alternates directions. For the first level, we go from left to right, for the next level we go from right to left, and we keep alternating in this fashion for subsequent levels. This process should continue until we have traversed all levels of the tree. The objective is to collect the values of the nodes level by level, adhering to the zigzag order described, and return them as a list of lists, where each internal list represents a level of the tree.

Intuition

To achieve the zigzag level-order traversal, we can utilize a queue data structure that helps us perform the modified level order traversal. We can manage the direction of traversal for each level by introducing a flag that indicates whether to reverse the nodes' values of the current level before adding them to the final answer list.

Here's a step-by-step breakdown of the approach:

1. Create an empty list ans to store the zigzag level order traversal.
2. Check if the input root is None. If it is, return the empty ans list as there are no nodes to traverse.
3. Initialize a queue using deque and add the root node to it. This queue will help in level order traversal.
4. Maintain a flag left to determine the direction of the zigzag. Initialize it to 1 which represents left to right order.
5. Enter a while loop that will run as long as there are nodes left in the queue:
   • Create a temporary list t to store the values of nodes at the current level.
   • Wihin the while loop, run another for loop that fetches each node of the current level from the queue:
     • Pop nodes from the left side of the queue (popleft) and append their value to t.
     • Add the left and right children of these nodes to the queue if they exist.
   • After the for loop, check the left flag. If it indicates right to left order (flag is 0), reverse the list t.
   • Append the list t, which represents the values at current level, to ans.
   • Toggle the left flag using bitwise XOR (left ^= 1) to switch the direction for the next level.
6. After the traversal is done and all levels are processed, return the ans list containing the zigzag level order traversal.

By following this procedure, we maintain the zigzag order by reversing every other level before appending it to our answer list, while the normal level order is achieved through the regular use of the queue.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution is implemented using the breadth-first search (BFS) algorithm, which is ideal for level order traversal in trees. BFS is typically implemented with a queue data structure that stores nodes at each level of the tree. Additionally, the solution employs a simple flag toggling mechanism to keep track of the zigzag pattern requirement and a deque structure from Python's collections module for efficient popping from both ends of the queue.

Here's a step-by-step walk-through of the code corresponding to the BFS algorithm and the modifications made to achieve zigzag level order traversal:

1. The Solution class contains the zigzagLevelOrder method, which takes 'root' of the binary tree as an input and returns a list of lists of integers representing the zigzag level order traversal.

2. An empty list ans is initialized to store the final zigzag traversal.

3. A check for the base case is performed where if 'root' is None, the method immediately returns the empty ans list.

4. A deque is initialized with the 'root' node. This queue (q) will be used for the BFS traversal, storing the nodes at each level.

5. The left flag is initialized to 1, representing the initial direction of traversal from left to right.

6. A while loop begins, which keeps running as long as there are nodes in the queue:

   • A temporary list t is created to store the nodes' values at the current level.

   • A for loop iterates over the current level's nodes present in the queue:

     • The method popleft is used to pop nodes from the left side of the queue to ensure FIFO (First-In-First-Out) order.

     • The value of the node is added to the temporary list t.

     • The node's left and right children are added to the queue if they are not None. This step ensures that the next level's nodes are added to the queue.

   • Once all nodes from the current level have been processed, a check is made for the left flag:

     • If left is 0, indicating that the current level should be traversed from right to left, the list t is reversed before being appended to ans.

     • If left is 1, list t is appended to ans as is.

   • The left flag is toggled using bitwise XOR (left ^= 1) to reverse the direction for the next level's traversal.

7. After all levels have been processed and the queue is empty, the while loop exits, and the method returns the ans list, which now contains the zigzag level order traversal.

The key to this solution is the combination of a typical BFS with the dynamic reversal of the levels' node values based on the left flag, which indicates the directive of traversal. The deque allows for efficient addition and removal of nodes during traversal, and toggling of left at each level effortlessly manages the zigzag pattern without any complex conditions or additional data structures.

Example Walkthrough

Let's consider a small binary tree example to walk through the solution approach described:

1        3
2       / \
3      9  20
4        /  \
5       15   7

We want to perform a zigzag level order traversal on the above tree. Here's how the approach is carried out:

1. Initialize an empty list ans to store the results. Also, check if the root is None. In this example, the root is 3, so we move forward.

2. Create a queue using deque and add the root to it. Our queue now contains the node 3.

3. Initialize the left flag to 1, signifying the direction of traversal. Since it's the first level, we will go from left to right.

4. Now we begin our while loop since the queue is not empty:

   • Initialize a temporary list t, which will hold nodes' values at the current level.
   • The number of iterations for the for loop is determined by the current queue's length, which is 1 (only node 3 is in it).
   • We pop node 3 using popleft, add its value to t, which becomes [3], and then enqueue its children, 9 and 20.
   • With the left flag set to 1, we do not need to reverse t, so we append [3] to ans.
   • Toggle the left flag using left ^= 1 so it now indicates that we should go from right to left on the next level.

5. Our queue now has two nodes, 9 and 20, and ans is [[3]].

6. The while loop runs again with the new queue:

   • We reset t to an empty list for the new level.
   • With 2 nodes in the queue, our for loop has 2 iterations.
   • We pop 9 and 20 using popleft, add their values to t, which becomes [9, 20], and enqueue their children (15 and 7 added to the queue).
   • Since the left flag is now 0, we reverse t before appending, so we append [20, 9] to ans.
   • The left flag is toggled again, so the next level will go from left to right.

7. Our queue now contains 15 and 7, and ans is [[3], [20, 9]].

8. The while loop continues for the next level with a similar process:

   • t is reset to an empty list.
   • There are 2 nodes in the queue.
   • We pop 15 and 7, add their values [15, 7] to t, and since there are no more children, we don't enqueue anything further.
   • The left flag is 1, so we append [15, 7] as is to ans.

9. Now the queue is empty, so the while loop ends.

10. We return ans which has recorded the zigzag level order traversal and the final result is [[3], [20, 9], [15, 7]].

Solution Implementation

Time and Space Complexity

The given Python code performs a zigzag (or spiral) level order traversal of a binary tree. Now let's analyze its time complexity and space complexity.

Time Complexity:

The time complexity of the algorithm is O(N), where N is the number of nodes in the binary tree. This is because the algorithm processes each node exactly once. Each node is added to and removed from the deque, the children are accessed, and the node's value is appended to the temporary list t.

Space Complexity:

The space complexity of the algorithm is O(N). This is the worst-case space required to hold all nodes in the queue when the last level of the tree is completely filled. In the case of a complete binary tree, the last level can contain up to N/2 nodes (for a perfectly balanced tree), which is still O(N) when we drop constants and lower-order terms. Additionally, the temporary list t, which stores nodes of a single level, can have at most N/2 nodes in the case of a complete binary tree. However, since t is reused for each level, it is not additive to the overall space complexity dominated by the queue.

Learn more about how to find time and space complexity quickly using problem constraints.