Binary Tree Zigzag Level Order Traversal - Leetcode Solution

Binary Tree Zigzag Level Order Traversal is a problem on LeetCode that requires us to find the zigzag level order traversal of a binary tree. In other words, we need to traverse the binary tree level by level, alternating the direction we go from left to right and right to left at each level.

To solve this problem, we will use a queue to keep track of the nodes in each level of the binary tree. We will also use a variable to keep track of whether we are currently traversing the level from left to right or from right to left.

Here is the step-by-step algorithm to solve the Binary Tree Zigzag Level Order Traversal problem:

1. Create an empty list called result, which will hold the zigzag level order traversal of the binary tree.

2. Create an empty queue called levelQueue, which will hold the nodes in the current level of the binary tree.

3. Create a variable called leftToRight, which will initially be set to True to indicate that we are currently traversing the first level from left to right.

4. Enqueue the root node of the binary tree into the levelQueue.

5. While the levelQueue is not empty, do the following:

a. Create a list called levelNodes, which will hold the nodes in the current level of the binary tree.

b. Get the size of the levelQueue and loop through it that many times. During each iteration, dequeue a node from the levelQueue and append it to the levelNodes list.

c. If leftToRight is True, reverse the order of the nodes in the levelNodes list.

d. Append the levelNodes list to the result list.

e. Loop through the nodes in the levelNodes list and enqueue their left and right children (if they exist) into the levelQueue.

f. Toggle the value of leftToRight to switch the direction of traversal for the next level.

6. Return the result list, which now contains the zigzag level order traversal of the binary tree.

Here is the Python code implementation of the above algorithm:

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

    result = []
    levelQueue = [root]
    leftToRight = True

    while levelQueue:
        levelNodes = []
        size = len(levelQueue)
        for i in range(size):
            node = levelQueue.pop(0)
            levelNodes.append(node)

            if node.left:
                levelQueue.append(node.left)
            if node.right:
                levelQueue.append(node.right)

        if not leftToRight:
            levelNodes.reverse()

        result.append([node.val for node in levelNodes])
        leftToRight = not leftToRight

    return result

The above code takes O(N) time and O(N) space complexity, where N is the number of nodes in the binary tree.

1