algoadvance

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:

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

Clarifying Questions

1. What should we return if the tree is empty?
   • If the tree is empty, we should return an empty list [].
2. Are all node values unique?
   • Yes, typically in binary tree traversal problems, all node values are unique, making it straightforward to handle.
3. How should we handle levels with None values/intermediate None nodes?
   • Since the traversal is only concerned with existing nodes, intermediate None values shouldn’t affect the traversal.

Strategy

1. Level Order Traversal: We can use a BFS (Breadth-First Search) approach for level order traversal. This involves using a queue to keep track of nodes at the current level, then processing nodes for the next level.

2. Zigzag Pattern: To implement the zigzag pattern, we use a flag (left_to_right) to toggle the order of traversal at each level. If left_to_right is true, append nodes’ values in normal order, otherwise append in reverse order.

3. Process:

   • Initialize a queue and begin with the root node.
   • Iterate until the queue is empty.
   • For each level, collect nodes’ values.
   • Depending on the left_to_right flag, either append or prepend these values to the result list.
   • Toggle the left_to_right flag after processing each level.

By the end of the traversal, we will have the nodes’ values in zigzag level order.

Code

from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root: TreeNode):
    if not root:
        return []

    results = []
    node_queue = deque([root])
    left_to_right = True

    while node_queue:
        level_size = node_queue.qsize()  # Number of nodes at the current level
        level_nodes = []
        
        for _ in range(level_size):
            node = node_queue.popleft()
            level_nodes.append(node.val)
            if node.left:
                node_queue.append(node.left)
            if node.right:
                node_queue.append(node.right)
        
        if not left_to_right:
            level_nodes.reverse()
        
        results.append(level_nodes)
        left_to_right = not left_to_right

    return results

Time Complexity

• Time Complexity: O(N)
  • Every node is visited exactly once, hence the time complexity is proportional to the number of nodes in the tree.
• Space Complexity: O(N)
  • In the worst case, the space needed for the queue will be proportional to the maximum number of nodes at any level of the tree, which is also O(N).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?