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.

Practice

1. What does Zigzag Level Order Traversal of a binary tree mean?

easy

A. Traverse nodes level by level, alternating left to right and right to left

B. Traverse nodes only from left to right at each level

C. Traverse nodes only from right to left at each level

D. Traverse nodes randomly without any order

Solution

1. Step 1: Understand level order traversal

   Level order traversal visits nodes level by level from left to right.

2. Step 2: Add zigzag pattern

   Zigzag means alternate direction each level: first left to right, then right to left, and so on.

3. Final Answer:

   Traverse nodes level by level, alternating left to right and right to left -> Option A

4. Quick Check:

   Zigzag = alternate directions [OK]

Hint: Remember zigzag means alternate directions each level [OK]

Common Mistakes:

• Thinking traversal is always left to right
• Confusing zigzag with preorder or inorder traversal
• Ignoring the alternating direction pattern

2. Which of the following C++ code snippets correctly initializes a queue for level order traversal?

easy

A. std::list q; q.push_front(root);

B. std::stack q; q.push(root);

C. std::vector q; q.push_back(root);

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

Solution

1. Step 1: Identify correct data structure for level order

   Level order traversal uses a queue to process nodes FIFO (first in, first out).

2. Step 2: Check code snippets

   std::queue q; q.push(root); uses std::queue and pushes root correctly. Others use stack, vector, or list incorrectly for this purpose.

3. Final Answer:

   std::queue q; q.push(root); -> Option D

4. Quick Check:

   Queue for level order = std::queue q; q.push(root); [OK]

Hint: Use queue for level order traversal, not stack or vector [OK]

Common Mistakes:

• Using stack instead of queue
• Using vector push_back but no FIFO behavior
• Using list with push_front which reverses order

3. What is the output of the zigzag level order traversal for this tree?

    1
   / \
  2   3
 / \   \
4   5   6

medium

A. [[1], [3, 2], [4, 5, 6]]

B. [[1], [2, 3], [6, 5, 4]]

C. [[1], [3, 2], [6, 5, 4]]

D. [[1], [2, 3], [4, 5, 6]]

Solution

1. Step 1: Traverse level 0 left to right

   Level 0 has node 1, so output is [1].

2. Step 2: Traverse level 1 right to left

   Level 1 nodes are 2 and 3. Zigzag means reverse order here: [3, 2].

3. Step 3: Traverse level 2 left to right

   Level 2 nodes are 4, 5, 6 from left to right: [4, 5, 6].

4. Final Answer:

   [[1], [3, 2], [4, 5, 6]] -> Option A

5. Quick Check:

   Zigzag levels alternate direction [OK]

Hint: Alternate direction each level starting left to right [OK]

Common Mistakes:

• Not reversing order on alternate levels
• Mixing node order at last level
• Confusing left and right child order

4. Identify the bug in this C++ snippet for zigzag traversal:

std::vector zigzagLevelOrder(TreeNode* root) {
  std::vector result;
  if (!root) return result;
  std::queue q;
  q.push(root);
  bool leftToRight = true;
  while (!q.empty()) {
    int size = q.size();
    std::vector<int> level(size);
    for (int i = 0; i < size; ++i) {
      TreeNode* node = q.front(); q.pop();
      int index = leftToRight ? i : size - i - 1;
      level[index] = node->val;
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    result.push_back(level);
  }
  return result;
}

medium

A. Using vector<int> level(size) instead of vector<int> level

B. Incorrect queue initialization

C. Missing toggle of leftToRight after each level

D. Not checking if root is null

Solution

1. Step 1: Analyze loop for toggling direction

   The variable leftToRight controls direction but is never changed inside the loop.

2. Step 2: Identify missing toggle

   Without toggling leftToRight = !leftToRight; after processing each level, zigzag pattern won't alternate.

3. Final Answer:

   Missing toggle of leftToRight after each level -> Option C

4. Quick Check:

   Toggle direction each level [OK]

Hint: Toggle direction flag after each level to alternate traversal [OK]

Common Mistakes:

• Forgetting to flip leftToRight boolean
• Incorrect indexing in level vector
• Not pushing child nodes properly

5. Given a binary tree, how would you modify the zigzag level order traversal to return a flat vector of node values instead of a vector of vectors? For example, for tree:

    1
   / \
  2   3
 /     \
4       5

The output should be: [1, 3, 2, 4, 5]

hard

A. Use a stack instead of queue to store nodes for zigzag traversal

B. Perform normal zigzag traversal, then flatten the result vectors into one vector

C. Traverse all nodes left to right ignoring zigzag pattern

D. Return only the last level nodes in zigzag order

Solution

1. Step 1: Perform standard zigzag traversal

   Use queue and toggle direction each level to get vector of vectors with zigzag order.

2. Step 2: Flatten the vector of vectors

   Combine all inner vectors into a single vector preserving order to get flat list.

3. Final Answer:

   Perform normal zigzag traversal, then flatten the result vectors into one vector -> Option B

4. Quick Check:

   Flatten zigzag levels to one vector [OK]

Hint: Flatten after zigzag traversal to get single list [OK]

Common Mistakes:

• Trying to zigzag directly into flat vector without levels
• Using stack incorrectly for zigzag
• Ignoring zigzag pattern and traversing left to right only