103. Binary Tree Zigzag Level Order Traversal

MediumTreeBreadth-First SearchBinary Tree

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.

Flowchart Walkthrough

Let's analyze the problem using the algorithm flowchart available at the Flowchart. Here's a detailed step-by-step explanation to determine the suitable algorithm:

Is it a graph?

Yes: Although not explicitly stated as a graph, a binary tree is a specific type of graph.

Is it a tree?

Yes: A binary tree is indeed a tree.

Using the BFS pattern is directly indicated as part of the Breadth-First Search utilities in tree related problems. BFS is traditionally used for level order traversal in trees, and in this particular problem (Zigzag Level Order Traversal), we use the BFS strategy but with an added mechanism to alter the direction of traversal at each level.

Conclusion: Based on the flowchart, Breadth-First Search (BFS) is apt for navigating through the levels of a binary tree, especially when direct level order is asked, regardless of the zigzag order requirement.

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:

Create an empty list ans to store the zigzag level order traversal.
Check if the input root is None. If it is, return the empty ans list as there are no nodes to traverse.
Initialize a queue using deque and add the root node to it. This queue will help in level order traversal.
Maintain a flag left to determine the direction of the zigzag. Initialize it to 1 which represents left to right order.
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.
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:

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.
An empty list ans is initialized to store the final zigzag traversal.
A check for the base case is performed where if 'root' is None, the method immediately returns the empty ans list.
A deque is initialized with the 'root' node. This queue (q) will be used for the BFS traversal, storing the nodes at each level.
The left flag is initialized to 1, representing the initial direction of traversal from left to right.
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.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

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

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.
Create a queue using deque and add the root to it. Our queue now contains the node 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.
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.
Our queue now has two nodes, 9 and 20, and ans is [[3]].
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.
Our queue now contains 15 and 7, and ans is [[3], [20, 9]].
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.
Now the queue is empty, so the while loop ends.
We return ans which has recorded the zigzag level order traversal and the final result is [[3], [20, 9], [15, 7]].

Solution Implementation

1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
12        # Initialize the result list
13        result = []
14      
15        # Return empty list if root is None
16        if root is None:
17            return result
18      
19        # Initialize a double-ended queue with the root node
20        queue = deque([root])
21      
22        # Variable to control the zigzag direction, starting with left as True
23        left_to_right = True
24      
25        # Loop until the queue is empty
26        while queue:
27            # Temporary list to store the values of the current level
28            level_values = []
29          
30            # Process all nodes at the current level
31            for _ in range(len(queue)):
32                # Pop a node from the left end of the deque
33                node = queue.popleft()
34                # Append the node's value to level_values
35                level_values.append(node.val)
36              
37                # Add the node's children to the queue
38                if node.left:
39                    queue.append(node.left)
40                if node.right:
41                    queue.append(node.right)
42          
43            # Append the current level's values to the result.
44            # Reverse the level_values if we are moving from right to left.
45            if left_to_right:
46                result.append(level_values)
47            else:
48                result.append(level_values[::-1])
49          
50            # Toggle the direction for the next level
51            left_to_right = not left_to_right
52      
53        # Return the zigzag level order traversal
54        return result
55

1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Collections;
4import java.util.Deque;
5import java.util.List;
6
7// Definition for a binary tree node
8class TreeNode {
9    int val;
10    TreeNode left;
11    TreeNode right;
12
13    TreeNode() {}
14
15    TreeNode(int val) {
16        this.val = val;
17    }
18
19    TreeNode(int val, TreeNode left, TreeNode right) {
20        this.val = val;
21        this.left = left;
22        this.right = right;
23    }
24}
25
26class Solution {
27    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
28        // List to hold the result
29        List<List<Integer>> result = new ArrayList<>();
30        // Return an empty list if the tree is empty
31        if (root == null) {
32            return result;
33        }
34      
35        // Queue to store the nodes for level order traversal
36        Deque<TreeNode> queue = new ArrayDeque<>();
37        queue.offer(root);
38      
39        // Flag for zigzag traversal direction
40        boolean leftToRight = true;
41      
42        // Perform level order traversal while queue is not empty
43        while (!queue.isEmpty()) {
44            // Temporary list to hold current level's values
45            List<Integer> tempList = new ArrayList<>();
46            // Process all nodes at the current level
47            for (int i = queue.size(); i > 0; --i) {
48                // Poll a node from the queue
49                TreeNode currentNode = queue.poll();
50                // Add the node's value to the temporary list
51                tempList.add(currentNode.val);
52                // Add the left child to the queue if it exists
53                if (currentNode.left != null) {
54                    queue.offer(currentNode.left);
55                }
56                // Add the right child to the queue if it exists
57                if (currentNode.right != null) {
58                    queue.offer(currentNode.right);
59                }
60            }
61          
62            // If the current direction is right to left, reverse the list
63            if (!leftToRight) {
64                Collections.reverse(tempList);
65            }
66            // Add the level's values to the result list
67            result.add(tempList);
68            // Toggle the zigzag direction
69            leftToRight = !leftToRight;
70        }
71      
72        // Return the final zigzag level order list
73        return result;
74    }
75}
76

1#include <vector>
2#include <queue>
3#include <algorithm>
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // Constructor
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // Constructor initializing all members
12};
13
14class Solution {
15public:
16    // Function to return zigzag level order traversal of a tree.
17    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
18        // The result will be stored in this vector of integer vectors.
19        vector<vector<int>> result;
20      
21        // Base case: if the root is null, return an empty vector.
22        if (!root) return result;
23      
24        // Queue to store tree nodes during level order traversal.
25        queue<TreeNode*> nodesQueue;
26        nodesQueue.push(root); // Initialize the queue with the root node.
27      
28        // Variable to keep track of the current zigzag direction.
29        bool isLeftToRight = true;
30      
31        // While there are nodes to process in the queue...
32        while (!nodesQueue.empty()) {
33            // Temporary vector to store one level's nodes' values.
34            vector<int> level;
35          
36            // For all nodes at the current level...
37            for (int n = nodesQueue.size(); n > 0; --n) {
38                // Retrieve the next node.
39                TreeNode* node = nodesQueue.front(); 
40                nodesQueue.pop();
41              
42                // Add the node's value to the current level vector.
43                level.push_back(node->val);
44              
45                // Add the node's left child to the queue if it exists.
46                if (node->left) nodesQueue.push(node->left);
47              
48                // Add the node's right child to the queue if it exists.
49                if (node->right) nodesQueue.push(node->right);
50            }
51          
52            // If the current direction is right to left, reverse the level vector.
53            if (!isLeftToRight) {
54                reverse(level.begin(), level.end());
55            }
56          
57            // Append the current level to the result vector.
58            result.push_back(level);
59          
60            // Toggle the direction for the next level.
61            isLeftToRight = !isLeftToRight;
62        }
63
64        // Return the zigzag level order traversal.
65        return result;
66    }
67};
68

1// TreeNode class definition
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8        this.val = val === undefined ? 0 : val;
9        this.left = left === undefined ? null : left;
10        this.right = right === undefined ? null : right;
11    }
12}
13
14/**
15 * Perform a zigzag level order traversal on a binary tree.
16 * 
17 * @param {TreeNode | null} root The root of the binary tree.
18 * @return {number[][]} A 2D array containing the values of the nodes at each level of the tree.
19 * Zigzag order begins with the leftmost node at level 0 and alternates with each subsequent level.
20 */
21function zigzagLevelOrder(root: TreeNode | null): number[][] {
22    // Result list to store the level order traversal.
23    const results: number[][] = [];
24    // Return empty list if the root is null.
25    if (root == null) {
26        return results;
27    }
28    // Flag to track the order of traversal; false implies left-to-right.
29    let isZigzag: boolean = false;
30    // Queue to facilitate level order traversal using Breadth-First Search (BFS).
31    const queue: TreeNode[] = [root];
32
33    // Continue until the queue is empty.
34    while (queue.length > 0) {
35        // Temporary list to store the current level's values.
36        const currentLevel: number[] = [];
37        // Iterate over the nodes at the current level.
38        let levelSize: number = queue.length;
39        for (let i = 0; i < levelSize; i++) {
40            // Dequeue a node from the front of the queue.
41            const currentNode: TreeNode = queue.shift()!;
42            // Add the node's value to the current level's list.
43            currentLevel.push(currentNode.val);
44            // Enqueue left and right children to the queue, if they exist.
45            if (currentNode.left) {
46                queue.push(currentNode.left);
47            }
48            if (currentNode.right) {
49                queue.push(currentNode.right);
50            }
51        }
52        // Add the current level's values to the result list, reversing if in zigzag order.
53        results.push(isZigzag ? currentLevel.reverse() : currentLevel);
54        // Invert the zigzag flag for the next level.
55        isZigzag = !isZigzag;
56    }
57
58    // Return the zigzag level order traversal.
59    return results;
60}
61

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls