Zigzag Level Order Traversal in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Level Order Traversal on a simple tree

What is the output of the following C++ code performing zigzag level order traversal on the given binary tree?

DSA C++

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

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

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

int main() {
    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->right = new TreeNode(6);

    vector<vector<int>> res = zigzagLevelOrder(root);
    for (auto& level : res) {
        for (int val : level) cout << val << " ";
        cout << "\n";
    }
    return 0;
}

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

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

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

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

💡 Hint

Remember that zigzag means alternating the order of nodes at each level.

The traversal starts left to right at level 0, so output is [1].

At level 1, the order is right to left, so nodes 3 and 2 are reversed to [3, 2].

At level 2, order is left to right again, so nodes 4, 5, 6 are in normal order.

🧠 Conceptual

intermediate

Understanding the role of deque in zigzag traversal

Why is a double-ended queue (deque) used in zigzag level order traversal instead of a regular queue?

A Because deque prevents duplicate nodes from being added.

B Because deque automatically sorts the nodes at each level.

C Because deque uses less memory than a regular queue.

D Because deque allows insertion and deletion from both ends, enabling reversal of traversal direction efficiently.

💡 Hint

Think about how zigzag traversal changes direction at each level.

Zigzag traversal requires visiting nodes from left to right on one level and right to left on the next.

A deque allows adding and removing nodes from both ends, making it easy to switch traversal direction without extra reversing steps.

❓ Predict Output

advanced

Output of zigzag traversal with null children nodes

What is the output of the following zigzag traversal code on the given tree with some null children?

DSA C++

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

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

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

int main() {
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->left->right = new TreeNode(40);
    root->right->left = new TreeNode(50);

    vector<vector<int>> res = zigzagLevelOrder(root);
    for (auto& level : res) {
        for (int val : level) cout << val << " ";
        cout << "\n";
    }
    return 0;
}

A [[10], [30, 20], [40, 50]]

B [[10], [20, 30], [50, 40]]

C [[10], [30, 20], [50, 40]]

D [[10], [20, 30], [40, 50]]

💡 Hint

Check the order of nodes at each level carefully, especially the last level.

Level 0: left to right → [10]

Level 1: right to left → [30, 20]

Level 2: left to right → children 40 and 50 in order [40, 50]

🔧 Debug

advanced

Identify the error in zigzag traversal code snippet

What error will the following code produce when performing zigzag level order traversal?

DSA C++

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    deque<TreeNode*> dq;
    dq.push_back(root);
    bool leftToRight = true;
    while (!dq.empty()) {
        int size = dq.size();
        vector<int> level(size);
        for (int i = 0; i < size; ++i) {
            TreeNode* node = dq.back();
            dq.pop_back();
            int index = leftToRight ? i : (size - 1 - i);
            level[index] = node->val;
            if (node->left) dq.push_front(node->left);
            if (node->right) dq.push_front(node->right);
        }
        leftToRight = !leftToRight;
        result.push_back(level);
    }
    return result;
}

A The code produces reversed output but no error.

B The code causes an infinite loop because nodes are added incorrectly.

C The code throws a runtime error due to accessing empty deque.

D The code runs correctly and returns the zigzag traversal.

💡 Hint

Check how nodes are added and removed from the deque inside the loop.

The code removes nodes from the back but adds children to the front in the same loop, causing the deque size to never reduce properly.

This leads to an infinite loop.

🚀 Application

expert

Number of nodes processed in zigzag traversal

Given a perfect binary tree of height 3 (levels 0 to 3), how many nodes will be processed in total during a zigzag level order traversal?

A 15

B 7

C 14

D 8

💡 Hint

Recall the total number of nodes in a perfect binary tree of height h is 2^(h+1) - 1.

A perfect binary tree of height 3 has 2^(3+1) - 1 = 15 nodes.

Zigzag traversal visits every node exactly once, so total processed nodes = 15.

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