Binary Tree Zigzag Level Order Traversal

Zigzag level order traversal is a fascinating variation of the standard breadth-first search (BFS) applied to binary trees. While a standard level order traversal visits nodes from left to right on every level, the zigzag approach alternates the direction: left-to-right on the first level, right-to-left on the second, left-to-right on the third, and so on. This pattern creates a "zigzag" visual effect, resembling the teeth of a saw or the path of a lightning bolt. Mastering this algorithm is a rite of passage for software engineers preparing for technical interviews, as it tests a candidate's ability to manipulate standard data structures—specifically queues and stacks—or to manage recursion with state tracking.

People argue about this. Here's where I land on it.

Understanding the Core Concept

At its heart, a binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. That's why traversing this structure level by level requires a mechanism to process all nodes at depth d before moving to depth d+1. The standard tool for this is a Queue (First-In-First-Out), which preserves the arrival order of nodes.

The twist in zigzag traversal lies in the output order of the values within each level. We still discover nodes in a standard left-to-right BFS manner (enqueue left child, then right child), but we must report their values in alternating directions. This distinction between discovery order and output order is the key to designing an efficient solution.

Approach 1: Two Stacks (The Intuitive Iterative Method)

One of the most elegant iterative solutions avoids reversing lists entirely by utilizing two stacks. Stacks operate on a Last-In-First-Out (LIFO) principle, which naturally reverses the order of elements pushed onto them.

The Logic

1. Stack 1 (Current Level): Stores nodes for the current level. We pop from this stack to process nodes.
2. Stack 2 (Next Level): Stores children of the current level's nodes for the next iteration.
3. Direction Flag: A boolean variable (leftToRight) tracks the current traversal direction.

The Algorithm Steps

1. Push the root node onto Stack 1. Set leftToRight = true.
2. While Stack 1 is not empty:
   • Create a temporary list levelValues to store values for the current level.
   • While Stack 1 is not empty:
     • Pop a node current from Stack 1.
     • Add current.val to levelValues.
     • Crucial Step: Push children onto Stack 2 based on leftToRight:
       • If leftToRight is true: Push Left child first, then Right child. (Because Stack is LIFO, Right will be popped first next time, achieving Right-to-Left).
       • If leftToRight is false: Push Right child first, then Left child. (Left will be popped first next time, achieving Left-to-Right).
   • Add levelValues to the final result list.
   • Swap Stack 1 and Stack 2 (Stack 2 becomes the new current level).
   • Toggle leftToRight.

Why This Works

When leftToRight is true, we want the next level to print Right-to-Left. By pushing Left then Right onto the stack, the Right child sits on top. When we pop in the next iteration, Right comes out first. The logic inverts perfectly for the opposite direction The details matter here. That's the whole idea..

Time Complexity: O(N) — Every node is pushed and popped exactly once. Space Complexity: O(N) — In the worst case (a perfect binary tree), the last level holds N/2 nodes.

Approach 2: Single Queue with Deque (The Modern Standard)

While the two-stack method is clever, the industry standard often favors a single Queue (for BFS ordering) combined with a Double-Ended Queue (Deque) for building the level list. This approach separates the traversal logic from the ordering logic, making the code cleaner and easier to maintain.

The Logic

We perform a standard BFS using a Queue. We track the size of the queue at the start of each level to know exactly how many nodes belong to that level. As we dequeue nodes, we add their values to a Deque. Depending on the direction flag, we either addLast (append right) or addFirst (prepend left).

The Algorithm Steps

1. Initialize result list and queue with root. Set leftToRight = true.
2. While queue is not empty:
   • Get levelSize = queue.size().
   • Initialize levelList as a Deque (e.g., LinkedList in Java, deque in Python, collections.deque).
   • Loop i from 0 to levelSize - 1:
     • Dequeue node.
     • If leftToRight: levelList.addLast(node.val).
     • Else: levelList.addFirst(node.val).
     • Enqueue node.left and node.right (if they exist) — always Left then Right.
   • Convert levelList to a standard List/Array and add to result.
   • Toggle leftToRight.

Advantages

• Child Enqueue Order is Constant: We always enqueue Left then Right. We don't need to swap push logic based on direction.
• Standard BFS Pattern: The outer loop structure is identical to standard level order traversal, reducing cognitive load.
• Efficiency: addFirst and addLast on a Deque are O(1) operations.

Approach 3: Depth-First Search (DFS) with Recursion

It is possible to solve this using DFS (Pre-order traversal) by passing the current level (depth) as a parameter to the recursive function. This approach builds the result list level by level as the recursion unwinds.

The Logic

1. Maintain a global or passed-by-reference result list (List of Lists).
2. Recursive function dfs(node, level):
   • Base case: If node is null, return.
   • If result.size() == level, it means we are visiting this depth for the first time. Add a new empty List/Deque to result.
   • Access result.get(level).
   • If level % 2 == 0 (Even level -> Left-to-Right): addLast(node.val).
   • Else (Odd level -> Right-to-Left): addFirst(node.val).
   • Recurse Left: dfs(node.left, level + 1).
   • Recurse Right: dfs(node.right, level + 1).

Trade-offs

• Pros: Code is extremely concise. No explicit queue/stack management needed.
• Cons: Uses the system Call Stack. For highly skewed trees (depth N), this risks Stack Overflow errors. Iterative approaches (Queue/Stack) use Heap memory, which is generally larger and safer for deep trees.

Python Implementation (Deque Approach)

Here is a clean, production-ready Python implementation using the collections.deque for both the node queue and the level value container.

from collections import deque
from typing import List, Optional

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

1.  **Analyze the Request:**
    *   **Goal:** Continue the article easily. Do not repeat previous text. Finish with a proper conclusion.
    *   **Input:** A partial article about "Binary Tree Level Order Traversal II" (or similar, based on the context of reversing levels, left-to-right vs right-to-left). The input ends abruptly with `self.left = left` and `self.right = right` (implied by standard LeetCode definition, though cut off). Wait, looking closely at the prompt: `self.left = left` is the end of the `TreeNode` class definition. It then cuts off. I need to complete the Python implementation and add a proper conclusion.
    *   **Tone/Style:** Technical, informative, clear, consistent with previous sections.
    *   **Constraint 1:** Seamless continuation. No repeating previous text.
    *   **Constraint 2:** Proper conclusion.

2.  **Review the Previous Text:**
    *   The text discusses three approaches: BFS with Queue (Left-to-Right), BFS with Deque (Left-to-Right), DFS with Recursion.
    *   It ends with the start of the Python implementation using `collections.deque`.
    *   I need to finish the `TreeNode` class, write the main function, and provide a conclusion.

3.  **Drafting the Continuation:**
    *   *Complete the TreeNode class:*
        ```python
        class TreeNode:
            def __init__(self, val=0, left=None, right=None):
                self.val = val
                self.left = left
                self.right = right
        ```
    *   *Write the main function:*
        ```python
        def reverseLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
            if not root:
                return []
            
            queue = deque([root])
            result = []
            
            while queue:
                level_size = len(queue)
                level_list = deque()
                
                for _ in range(level_size):
                    node = queue.popleft()
                    # Odd levels go Right-to-Left, so we prepend
                    if result.index(result) % 2 == 1 or True: # wait, this logic is for DFS. For BFS, we just check level parity.
                        pass
                ```
        *Correction for BFS approach in Python:*
        Wait, the text says "Approach 2: BFS with Deque". Let's write that correctly.
        ```python
        def reverseLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
            if not root:
                return []
            
            queue = deque([root])
            result = []
            
            while queue:
                level_size = len(queue)
                level_list = deque()
                
                for _ in range(level_size):
                    node = queue.popleft()
                    level_list.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                
                # If the current level index is odd, we reversed it during traversal?
                # Actually, if we want to output Right-to-Left for odd levels, 
                # we can either reverse the level_list before appending, or build it Left-to-Right and reverse at the end.
                # But the prompt's Approach 2 logic said: "If leftToRight: addLast. Else: addFirst."
                # So I should implement exactly that logic.
                ```
        Let's refine the BFS approach code to match the described logic.
        ```python
        def reverseLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
            if not root:
                return []
            
            queue = deque([root])
            result = []
            left_to_right = True
            
            while queue:
                level_size = len(queue)
                level_list = deque()
                
                for _ in range(level_size):
                    node = queue.popleft()
                    if left_to_right:
                        level_list.append(node.val)
                    else:
                        level_list.appendleft(node.val)
                    
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                
                result.append(list(level_list))
                left_to_right = not left_to_right
                
            return result
        ```
        Wait, standard level order is usually even levels L->R, odd levels R->L.
        If `root` is level 0 (even), L->R.
        Level 1 (odd), R->L.
        So `left_to_right` starts True. Even levels append last. Odd levels append first. This matches perfectly.

4.  **Drafting the Conclusion:**
    *   Summarize the trade-offs of the three approaches.
    *   Mention which