L19. Zig-Zag or Spiral Traversal in Binary Tree | C++ | Java

1. Why Do We Need Zig-Zag Traversal? (Problem Statement & Status Quo)

In standard Level Order Traversal (Breadth-First Search / BFS), nodes are visited strictly level by level from left to right:

Level 0: [1]
Level 1: [2, 3]
Level 2: [4, 5, 6]

While standard BFS is powerful, certain applications require a Zig-Zag (or Spiral) Traversal. In this pattern, the traversal direction alternates with every level:

Level 0 (Left to Right): [1]
Level 1 (Right to Left): [3, 2]
Level 2 (Left to Right): [4, 5, 6]

The core challenge is maintaining this alternating directional flow efficiently without completely rewriting our standard BFS infrastructure.

2. Core Mental Model & Analogy

Real-Life Analogy: Imagine inspecting items on a conveyor belt or shelving books in a warehouse aisle. Instead of always walking back to the left side of the room to start the next shelf, you walk back and forth: down the first aisle left-to-right, turn around and walk down the second aisle right-to-left, then turn around again.

To implement this computationally:

We use a standard Queue to process nodes level by level (just like normal BFS).
We introduce a Flag Variable (boolean or binary integer) that toggles between true/false (or 1/0) after every completed level.
Depending on the flag state, we place current level elements into our temporary row storage either from left-to-right or right-to-left.

3. Standard Level Order vs. Zig-Zag Evolution

Let's examine how we transition from regular level-order collection to zig-zag collection.

Structure & Concept Flow

Standard Level Order:

Level 1: [2, 3] -> Insert normally: index 0 gets 2, index 1 gets 3.

Zig-Zag Variation:

Level 1 (Right-to-Left Flag Active):

- Node 2 is popped -> placed at current index (or calculated offset).

- Node 3 is popped -> placed such that it appears *before* 2, resulting in [3, 2].

By leveraging a dynamic data structure for our row container (like a deque or pre-allocated array where we assign indices directly), we can control insertion order without expensive full-row sorting or reverse operations.

4. Step-by-Step Execution Walkthrough

Consider a binary tree with root 1, left child 2, right child 3. Node 2 has left child 4, right child 5. Node 3 has right child 6.

CODE

Initialization:

Queue (q): Push root (1). q = [1]
Result Container (result): Empty list of lists.
Flag (leftToRight): Set to true (1).

Level 0 Processing:

Queue size is 1.
Pop 1. Since leftToRight is true, insert 1 into the current level list normally. Result row: [1].
Push children of 1 into queue: 2 (left), then 3 (right). q = [2, 3].
Toggle leftToRight to false (0).
Append row [1] to result.

Level 1 Processing:

Queue size is 2 (nodes 2 and 3).
Iterate i from 0 to 1:
- Pop 2. Push its children (4, 5) into queue. Because leftToRight is false, we place 2 at the calculated reverse index in our row array (or insert at front).
- Pop 3. Push its right child (6) into queue. Place 3 ahead of 2.
Current level row becomes: [3, 2].
Toggle leftToRight back to true (1).
Append row [3, 2] to result. q = [4, 5, 6].

Level 2 Processing:

Queue size is 3 (nodes 4, 5, 6).
Pop 4, 5, 6. None have children.
Since leftToRight is true, insert normally: [4, 5, 6].
Queue is now empty. Loop terminates.

5. Complete C++ Implementation

C++

#include <iostream>
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;

        while (!q.empty()) {
            int size = q.size();
            vector<int> row(size);

            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();

                // Find position to fill based on flag
                int index = leftToRight ? i : (size - 1 - i);

                row[index] = node->val;

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            // Toggle flag for the next level
            leftToRight = !leftToRight;
            result.push_back(row);
        }

        return result;
    }
};

6. Complete Java Implementation

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean leftToRight = true;

        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> row = new ArrayList<>(Collections.nCopies(size, 0));

            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();

                // Determine index placement based on current direction flag
                int index = leftToRight ? i : (size - 1 - index); // Correct index logic: size - 1 - i
                
                // Let's write the explicit index assignment cleanly:
                int targetIndex = leftToRight ? i : (size - 1 - i);
                row.set(targetIndex, node.val);

                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }

            // Switch direction flag for subsequent level
            leftToRight = !leftToRight;
            result.add(row);
        }

        return result;
    }
}

Note: By initializing row with fixed size and setting elements via calculated indices (size - 1 - i), we avoid costly explicit collection reversals, achieving optimal $O(N)$ runtime performance.

7. Complexity Analysis

Complexity Type	Order	Rationale
Time Complexity	$O(N)$	Every node in the binary tree is visited exactly once during the queue traversal.
Space Complexity	$O(N)$	The queue holds at most all nodes of the widest level in the binary tree (in a complete binary tree, roughly $N/2$ leaf nodes), and the result structure stores $N$ total integers.

Summary and Key Takeaways

Core Objective: Traverse a binary tree level-by-level while alternating the horizontal direction of node collection between left-to-right and right-to-left.
Data Structure Foundation: Built directly on standard Breadth-First Search (BFS) utilizing a Queue data structure.
Direction Tracking: A boolean flag (leftToRight) toggles between true and false at the boundary of every level transition.
Smart Index Calculation: Instead of reversing lists dynamically, determining placement via index = leftToRight ? i : (size - 1 - i) optimizes runtime efficiency.
Queue Operations: Child nodes are always pushed into the queue in standard left-to-right order regardless of the current traversal direction, maintaining structural tree integrity.
Time & Space Efficiency: Both time and space complexities remain optimal at $O(N)$ , matching standard level-order traversal benchmarks.