Problem Statement

Given the root of 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).

Examples

Example 1:

Input : root = [1, 2, 3, null, 4, 8, 5]
Output : [ [1] , [3, 2], [4, 8, 5] ]

Explanation : So at root we move from left to right.
At next level we move in opposite direction i.e. from right to left.
At next level again reverse the traversal i.e. from left to right.

Example 2:

Input : root = [3, 9, 20, null, null, 15, 7]
Output : [ [3] , [20, 9], [15, 7] ]

Explanation : So at root we move from left to right.
At next level we move in opposite direction i.e. from right to left , from 20 to 9.
At next level again reverse the traversal i.e. from left to right, from 15 to 7.

Different Approaches

1️⃣ Using Queue

Intuition:

Zigzag traversal of a binary tree is an enhancement of the conventional level order traversal. While level order traversal explores nodes at each level from left to right, zigzag traversal adds an alternating pattern to the process. At odd levels, nodes are processed from left to right, but at even levels, the order is reversed, processing nodes from right to left. This alternation is controlled by a `leftToRight` flag, which determines the direction of node processing at each level. When `leftToRight` is true, nodes are inserted into the level vector from left to right, and when false, nodes are inserted from right to left.

Approach:

1. Begin by initializing an empty queue for node storage during traversal and a 2D vector to capture the level order traversal. If the binary tree is empty, return this empty 2D vector immediately. Additionally, create a leftToRight flag to track the traversal direction. When leftToRight is true, nodes are inserted into the level vector from left to right; when false, they are inserted from right to left.
2. Enqueue the root node of the binary tree into the queue to start the traversal.
3. Proceed with the following steps while the queue is not empty:
   1. Determine the current size of the queue, which reflects the number of nodes present at the current level of the tree.
   2. Create a vector named level to store the nodes' values at the current level.
   3. For each node at the current level, remove the front node from the queue, store its value in the level vector (inserting from left to right if leftToRight is true, or from right to left if false), and enqueue its child nodes (if they exist).
4. After processing all nodes at the current level, append the level vector to the ans 2D vector. Toggle the leftToRight flag to reverse the traversal direction for the subsequent level.
5. After all levels have been processed, return the ans 2D vector, which contains the zigzag level-order traversal of the binary tree.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        // Vector to store the result of zigzag traversal
        vector<vector<int>> result;

        // Check if the root is NULL, return an empty result
        if (root == nullptr) {
            return result;
        }

        // Queue to perform level order traversal
        queue<TreeNode*> nodesQueue;
        nodesQueue.push(root);

        // Flag to determine the direction of traversal (left to right or right to left)
        bool leftToRight = true;

        // Continue traversal until the queue is empty
        while (!nodesQueue.empty()) {
            // Get the number of nodes at the current level
            int size = nodesQueue.size();

            // Vector to store the values of nodes at the current level
            vector<int> row(size);

            // Traverse nodes at the current level
            for (int i = 0; i < size; i++) {
                // Get the front node from the queue
                TreeNode* node = nodesQueue.front();
                nodesQueue.pop();

                // Determine the index to insert the node's value based on the traversal direction
                int index = leftToRight ? i : (size - 1 - i);

                // Insert the node's value at the determined index
                row[index] = node->data;

                // Enqueue the left and right children if they exist
                if (node->left) {
                    nodesQueue.push(node->left);
                }
                if (node->right) {
                    nodesQueue.push(node->right);
                }
            }

            // Switch the traversal direction for the next level
            leftToRight = !leftToRight;

            // Add the current level's values to the result vector
            result.push_back(row);
        }

        // Return the final result of zigzag level order traversal
        return result;
    }
};

// Helper function to print the result
void printResult(const vector<vector<int>>& result) {
    for (const auto& row : result) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
}

int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    Solution solution;

    // Get the zigzag level order traversal
    vector<vector<int>> result = solution.zigzagLevelOrder(root);

    // Print the result
    printResult(result);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) where N is the number of nodes in the binary tree. Each node of the binary tree is enqueued and dequeued exactly once, hence all nodes need to be processed and visited.
• Space Complexity: O(N) where N is the number of nodes in the binary tree. In the worst case, the queue has to hold all the nodes of the last level of the binary tree, the last level could at most hold N/2 nodes hence the space complexity of the queue is proportional to O(N).