Technical Interview Question

Problem: You are 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).

For example, the input binary tree structure is:

    3
   / \
  9  20
    /  \
   15   7

The zigzag level order traversal of this tree would look like:

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

Write a function zigzagLevelOrder to solve this problem in Python.

Function Signature:

def zigzagLevelOrder(root: TreeNode) -> List[List[int]]:

Answer

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

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

        result = []
        queue = [root]
        level = 0

        while queue:
            level_values = []
            n = len(queue)
            
            for _ in range(n):
                node = queue.pop(0)
                level_values.append(node.value)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            if level % 2 == 1:
                level_values = level_values[::-1]

            result.append(level_values)
            level += 1

        return result

Explanation:

1. We start by checking whether the input root is none. If root is none, we return an empty list as there are no levels to traverse.
2. We initialize an empty result list to store the final zigzag order traversal.
3. We also initialize a queue with the root node and a variable level to keep track of the current level.
4. We then enter a while loop that continues until there is no node left in the queue.
5. Inside the while loop, we initialize an empty list level_values to store the values of nodes at the current level.
6. We use a for loop to iterate over the nodes in the current level. At each iteration:
   • We pop the first node from the queue and append its value to level_values.
   • If the popped node has a left child, we append it to the queue.
   • If the popped node has a right child, we append it to the queue.
7. After processing all nodes in the current level, we check if the level is odd. If it is odd, we reverse the level_values list to achieve zigzag traversal effect.
8. We append the level_values list to the final result list.
9. Finally, we increment the level and continue the process until the queue is empty.
10. At the end of the while loop, we return the result list containing the zigzag order traversal of the binary tree. This solution has a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the binary tree.