LeetCode 103: Binary Tree Zigzag Level Order Traversal Solution in Python Explained

Problem Statement

In LeetCode 103, you’re given the root of a binary tree. Your task is to return its zigzag level-order traversal—a list where each element is a list of node values at a given level, ordered left-to-right for even levels (starting at 0) and right-to-left for odd levels. This extends LeetCode 102: Binary Tree Level Order Traversal, adding the zigzag twist.

Constraints

• Number of nodes: 0 <= n <= 2000
• Node values: -100 <= Node.val <= 100

Example

Let’s see some cases:

Copy codeInput: root = [3,9,20,null,null,15,7]
      3
     / \
    9  20
       / \
      15  7
Output: [[3],[20,9],[15,7]]
Explanation: Level 0 (L->R): [3], Level 1 (R->L): [20,9], Level 2 (L->R): [15,7].

Copy codeInput: root = [1]
Output: [[1]]
Explanation: Level 0 (L->R): [1].

Copy codeInput: root = []
Output: []
Explanation: Empty tree, no levels.

These examples show we’re traversing levels with alternating directions.

Understanding the Problem

How do you solve LeetCode 103: Binary Tree Zigzag Level Order Traversal in Python? Take root = [3,9,20,null,null,15,7]. We need [[3],[20,9],[15,7]]—level 0 (left-to-right: 3), level 1 (right-to-left: 20,9), level 2 (left-to-right: 15,7). This isn’t a symmetry check like LeetCode 101: Symmetric Tree; it’s about level-order traversal with a zigzag pattern. We’ll use: 1. Queue-Based BFS with Direction: O(n) time, O(w) space—our best solution. 2. DFS with Level Tracking: O(n) time, O(h) space—an alternative.

Let’s dive into the best solution.

Best Solution: Queue-Based BFS with Direction Approach

Explanation

Queue-Based BFS with Direction processes the tree level-by-level using a queue, tracking the direction (left-to-right or right-to-left) for each level. For each level, collect node values, enqueue children, and reverse the level list if needed based on direction. This is the best solution due to its efficiency, natural fit for level-order traversal, and clear handling of the zigzag requirement.

For [3,9,20,null,null,15,7]:

• Level 0 (L->R): Queue [3], pop 3, add [9,20], result [[3]].
• Level 1 (R->L): Queue [9,20], pop 9,20, add [15,7], reverse [9,20] → [[3],[20,9]].
• Level 2 (L->R): Queue [15,7], pop 15,7, result [[3],[20,9],[15,7]].

Step-by-Step Example

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

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

Goal: Return [[3],[20,9],[15,7]].

• Start: queue = deque([3]), result = [], left_to_right = True.
• Step 1: Level 0 (L->R).
• Size = 1, level = [].
• Pop 3, level = [3], add 9,20 → queue = [9,20].
• left_to_right = True, no reverse, result = [[3]].
• Toggle: left_to_right = False.
• Step 2: Level 1 (R->L).
• Size = 2, level = [].
• Pop 9, level = [9], no children.
• Pop 20, level = [9,20], add 15,7 → queue = [15,7].
• left_to_right = False, reverse to [20,9], result = [[3],[20,9]].
• Toggle: left_to_right = True.
• Step 3: Level 2 (L->R).
• Size = 2, level = [].
• Pop 15, level = [15], no children.
• Pop 7, level = [15,7], no children.
• left_to_right = True, no reverse, result = [[3],[20,9],[15,7]].
• Finish: Return [[3],[20,9],[15,7]].

Example 2: root = [1]

Goal: Return [[1]].

• Start: queue = deque([1]), result = [].
• Step 1: Level 0 (L->R).
• Size = 1, level = [1], no children.
• result = [[1]].
• Finish: Return [[1]].

Example 3: root = []

Goal: Return [].

• Start: queue = deque([]).
• Step 1: Queue empty, result = [].
• Finish: Return [].

How the Code Works (Queue-Based BFS with Direction) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codefrom collections import deque

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

def zigzagLevelOrder(root: TreeNode) -> list[list[int]]:
    # Line 1: Check if root is null
    if not root:
        # If root is None, return empty list (e.g., [])
        return []

    # Line 2: Initialize result list
    result = []
    # Stores level lists (e.g., initially [])

    # Line 3: Initialize queue with root
    queue = deque([root])
    # deque for efficient operations (e.g., [3])

    # Line 4: Initialize direction flag
    left_to_right = True
    # True = left-to-right, False = right-to-left (e.g., starts True)

    # Line 5: Process levels while queue has nodes
    while queue:
        # Continues until all levels are processed (e.g., queue not empty)

        # Line 6: Get number of nodes in current level
        level_size = len(queue)
        # Size of current level (e.g., 1 for [3], 2 for [9,20])

        # Line 7: Initialize list for current level
        level = []
        # Collects values for this level (e.g., initially [])

        # Line 8: Process all nodes in current level
        for _ in range(level_size):
            # Loops level_size times (e.g., 1, then 2)

            # Line 9: Pop node from queue
            node = queue.popleft()
            # Removes and gets next node (e.g., 3, then 9, 20)

            # Line 10: Add node value to level
            level.append(node.val)
            # Adds value to current level (e.g., level=[3])

            # Line 11: Add left child if exists
            if node.left:
                queue.append(node.left)
                # Enqueues left child (e.g., 9 for root=3)

            # Line 12: Add right child if exists
            if node.right:
                queue.append(node.right)
                # Enqueues right child (e.g., 20 for root=3)

        # Line 13: Adjust level based on direction
        if not left_to_right:
            level.reverse()
            # Reverses if right-to-left (e.g., [9,20] → [20,9])

        # Line 14: Add level to result
        result.append(level)
        # Adds level list (e.g., [[3]], then [[3],[20,9]])

        # Line 15: Toggle direction
        left_to_right = not left_to_right
        # Switches direction for next level (e.g., True → False)

    # Line 16: Return final zigzag traversal
    return result
    # Returns complete list (e.g., [[3],[20,9],[15,7]])

This detailed breakdown clarifies how queue-based BFS with direction efficiently constructs the zigzag traversal.

Alternative: DFS with Level Tracking Approach

Explanation

DFS with Level Tracking traverses the tree depth-first, tracking each node’s level and building the result list. Reverse odd-level lists after traversal. It’s a useful alternative, leveraging recursion to visit nodes while organizing by level.

For [3,9,20,null,null,15,7]:

• DFS: 3 (0), 9 (1), 20 (1), 15 (2), 7 (2).
• Result: [[3],[9,20],[15,7]], reverse level 1 → [[3],[20,9],[15,7]].

Step-by-Step Example (Alternative)

For [3,9,20,null,null,15,7]:

• Start: result = [], dfs(3, 0).
• Step 1: 3, level 0, result = [[3]].
• Step 2: 9, level 1, result = [[3],[9]].
• Step 3: 20, level 1, result = [[3],[9,20]].
• Step 4: 15, level 2, result = [[3],[9,20],[15]].
• Step 5: 7, level 2, result = [[3],[9,20],[15,7]].
• Step 6: Reverse odd levels, level 1 → [20,9].
• Finish: [[3],[20,9],[15,7]].

How the Code Works (DFS with Level Tracking)

Copy codedef zigzagLevelOrderDFS(root: TreeNode) -> list[list[int]]:
    result = []
    def dfs(node: TreeNode, level: int):
        if not node:
            return
        if len(result) <= level:
            result.append([])
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    for i in range(1, len(result), 2):
        result[i].reverse()
    return result

Complexity

• Queue-Based BFS with Direction:
• Time: O(n) – visits each node once.
• Space: O(w) – queue size, w = max width.
• DFS with Level Tracking:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.

Efficiency Notes

Queue-Based BFS with Direction is the best solution with O(n) time and O(w) space, perfectly suited for zigzag traversal—DFS with Level Tracking matches time complexity with O(h) space, offering a recursive approach that’s adaptable but requires post-processing.

Key Insights

• Zigzag: Alternate directions per level.
• BFS: Level-by-level control.
• DFS: Depth-first with reversal.

Additional Example

For root = [1,2,3,4,null,5]:

• Goal: [[1],[3,2],[4,5]].
• BFS: Level 0: [1], Level 1: [3,2], Level 2: [4,5].

Edge Cases

• Empty Tree: [] → [].
• Single Node: [1] → [[1]].
• Unbalanced: [1,2,null,3] → [[1],[2],[3]].

Both solutions handle these well.

Final Thoughts

LeetCode 103: Binary Tree Zigzag Level Order Traversal in Python is an engaging twist on traversal. The Queue-Based BFS with Direction solution excels with its efficiency and clarity, while DFS with Level Tracking offers a recursive alternative. Want more? Try LeetCode 102: Binary Tree Level Order Traversal for standard order or LeetCode 94: Binary Tree Inorder Traversal for inorder basics. Ready to practice? Solve LeetCode 103 on LeetCode with [3,9,20,null,null,15,7], aiming for [[3],[20,9],[15,7]]—test your skills now!