Zigzag Level Order Traversal in DSA C++ - Build from Scratch

Zigzag Level Order Traversal

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to visit each generation, but in a zigzag way: first from left to right, then right to left, and so on. This helps you see the family members in a fun, alternating order.

🎯 Goal: Build a program that takes a binary tree and prints its nodes in zigzag level order traversal.

📋 What You'll Learn

Create a binary tree with the exact nodes and structure given.

Use a variable to track the current traversal direction (left to right or right to left).

Implement the zigzag level order traversal using a queue and direction toggling.

Print the final zigzag traversal as a list of lists.

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in scenarios like visualizing hierarchical data with alternating directions for better readability.

💼 Career

Understanding tree traversals and queue usage is essential for software engineering roles involving data structures and algorithms.

1

Create the binary tree nodes

Create the binary tree nodes exactly as follows: root node with value 1, root's left child with value 2, root's right child with value 3, node 2's left child with value 4, and node 3's right child with value 5. Use the struct TreeNode with int val, TreeNode* left, and TreeNode* right. Initialize all pointers to nullptr.

DSA C++

#include 
#include 
#include 

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

int main() {
    // Create root node with value 1
    // Create left child of root with value 2
    // Create right child of root with value 3
    // Create left child of node 2 with value 4
    // Create right child of node 3 with value 5
    // Your code here
    return 0;
}

Hint

Use new TreeNode(value) to create nodes and assign them to the correct pointers.

2

Add a direction flag for zigzag traversal

Add a boolean variable called leftToRight and set it to true. This variable will help track the current direction of traversal.

DSA C++

#include 
#include 
#include 

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

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    // Add a boolean variable leftToRight and set it to true
    // Your code here
    return 0;
}

Hint

Use bool leftToRight = true; to create the direction flag.

3

Implement zigzag level order traversal

Write the code to perform zigzag level order traversal on the binary tree starting from root. Use a queue<TreeNode*> to process nodes level by level. For each level, create a vector levelNodes of size equal to the number of nodes at that level. Insert node values into levelNodes from left to right if leftToRight is true, otherwise from right to left. After processing each level, toggle leftToRight to its opposite value. Store each levelNodes vector into a vector of vectors called result.

DSA C++

#include 
#include 
#include 

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

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    bool leftToRight = true;

    // Implement zigzag level order traversal using queue and leftToRight
    // Your code here

    return 0;
}

Hint

Use a queue to process nodes level by level. Use the leftToRight flag to decide the index to insert node values in levelNodes. Toggle leftToRight after each level.

4

Print the zigzag traversal result

Print the result vector of vectors in the format: each level's values separated by spaces, each level on a new line. Use nested for loops to iterate over result and print the values.

DSA C++

#include 
#include 
#include 

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

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    bool leftToRight = true;
    std::vector> result;
    if (!root) return 0;

    std::queue q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        std::vector levelNodes(size);
        for (int i = 0; i val;

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(levelNodes);
        leftToRight = !leftToRight;
    }

    // Print the result vector of vectors
    // Your code here

    return 0;
}

Hint

Use nested for loops to print each level's values separated by spaces, then print a newline after each level.