Zigzag Traversal of a Binary Tree

Zigzag Traversal of a Binary Tree

January 14, 2024
medium
BFS, grah

Problem #

Given 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:

  1. Input: 
        3
   / \
  9  20
    /  \
   15   7
    Output: [[3], [20, 9], [15, 7]]

Solution Approach #

The solution uses a breadth-first search (BFS) approach with a queue, alternating the direction of traversal with each level of the tree.

Algorithm Steps #

  1. Initialize a queue for BFS and add the root node.
  2. Keep a flag leftToRight to determine the direction of traversal for each level.
  3. While the queue is not empty, process the nodes level by level:
    • Determine the number of nodes at the current level.
    • Based on leftToRight, append nodes’ values from left to right or right to left.
    • For each node, add its children to the queue.
    • Invert leftToRight at the end of each level.
  4. Add the values collected for each level to the result list.
  5. Return the result list containing the zigzag level order traversal.

Code (Python) # 

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

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

    result = []
    queue = [root]
    leftToRight = True

    while queue:
        level = []
        levelSize = len(queue)
        for i in range(levelSize):
            node = queue.pop(0)
            if leftToRight:
                level.append(node.val)
            else:
                level.insert(0, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
        leftToRight = not leftToRight

    return result

# Test the function
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(zigzagLevelOrder(root))  # Output: [[3], [20, 9], [15, 7]]

Time Complexity #

O(n), where n is the number of nodes in the tree. Each node is processed exactly once.

Space Complexity #

O(n), primarily for the queue used in the BFS.