Binary Tree Zigzag Level Order Traversal medium

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).

Example 1

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

Example 2

Input: root = [1] Output: [[1]]

Steps

1. Initialization: Create a queue q to perform a level-order traversal and an empty vector result to store the zigzag traversal. We also need a variable leftToRight to keep track of the traversal direction (true for left-to-right, false for right-to-left).

2. Level Order Traversal: Start by adding the root node to the queue. While the queue is not empty, perform the following steps:

   • Get the number of nodes at the current level (size of the queue).
   • Create a vector level to store nodes at this level.
   • Iterate through the nodes at the current level:
     • If leftToRight is true, add the nodes from left to right.
     • If leftToRight is false, add the nodes from right to left. This is done by processing the nodes in reverse order.
   • Add the level to result.
   • For each node processed, add its children (if any) to the queue.
   • Toggle leftToRight for the next level.

3. Return Result: Finally, return the result vector containing the zigzag level order traversal.

Explanation

The algorithm utilizes a level-order traversal (BFS) to traverse the binary tree level by level. The key is the leftToRight flag, which is toggled at the end of each level. This flag determines the order in which nodes are added to the level vector. If leftToRight is true, nodes are added from left to right (standard level-order); otherwise, they're added from right to left, achieving the zigzag effect.

Code

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

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 levelSize = q.size();
        vector<int> level;
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            if (leftToRight) {
                level.push_back(node->val);
            } else {
                level.insert(level.begin(), node->val); // Insert at beginning for right-to-left
            }
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
        leftToRight = !leftToRight; // Toggle direction
    }
    return result;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited and processed exactly once.
• Space Complexity: O(W), where W is the maximum width of the binary tree. In the worst case (a complete binary tree), this could be O(N). The space is primarily used by the queue to store nodes during the level order traversal.