ZigZag Level Order Traversal [DSA — Tree Problem]

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).

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[9,20],[15,7]]

Input

Solution:

Intuition:

To solve the Zigzag Level Order Traversal problem, we first ask ourselves:

What is the natural way to process a tree level by level?

The answer is breadth-first search (BFS), because BFS explores one level at a time using a queue.

But then comes the twist: How do we introduce the zigzag pattern?

Normally, BFS processes nodes from left to right at every level.

However, in this problem, we want to alternate directions left to right for one level, then right to left for the next.

So the next question is: How can we alternate directions without breaking the BFS process? One idea is to use a flag or counter. If the current level is even, we keep the order as it is. If the level is odd, we reverse the collected values before adding them to the result.

This way, the BFS traversal remains intact, but by simply checking the level number (even or odd), we achieve the zigzag effect.

level order traversal explanation

Steps:

1. Initialize a queue to store nodes for each level, a result list to store the final traversal, and a counter to track the level number.

2. Add the root node to the queue.

3. While the queue is not empty:

• a. Get the number of nodes in the current level.
• b. Create an empty list to store the current level’s values.
• c. For each node in this level:
• i. Remove the node from the queue.
• ii. Add the node’s value to the current level’s list.
• iii. If the node has a left child, add it to the queue.
• iv. If the node has a right child, add it to the queue.
• d. If the level counter is odd, reverse the current level’s list.
• e. Add the current level’s list to the result.
• f. Increment the level counter.

4. Return the result list.

Code:

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

        q = deque()
        if root is None:
            return []
        q.append(root)
        res = []
        counter = 0
        while len(q) > 0:
            n = len(q)
            ans = []
            for i in range(n):
                ele = q.popleft()
                if ele.left is not None:
                    q.append(ele.left)
                if ele.right is not None:
                    q.append(ele.right)
                ans.append(ele.val)
            if counter % 2 == 1:
                res.append(ans[::-1])
            else:
                res.append(ans)
            counter += 1

        return res

Analysis:

Time Complexity: O(N) where N is the number of nodes in the binary tree.

Space Complexity: O(N) for the queue used in BFS traversal.