Zigzag Level Order Traversal in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the result vector for storing levels.

DSA C++

vector<vector<int>> [1];

Drag options to blanks, or click blank then click option'

Aresult

Blevels

Coutput

Dzigzag

Attempts:

3 left

💡 Hint

Common Mistakes

Using a single vector instead of vector>

Naming the variable something unrelated

The vector named 'result' is commonly used to store the final zigzag level order traversal.

2fill in blank

medium

Complete the code to check if the current level should be reversed.

DSA C++

if (level % 2 == [1]) { reverse(currentLevel.begin(), currentLevel.end()); }

Drag options to blanks, or click blank then click option'

A0

B1

C2

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Reversing even levels instead of odd

Using incorrect modulus value

Odd levels (level % 2 == 1) are reversed to achieve zigzag order.

3fill in blank

hard

Fix the error in the queue push operation for left and right children.

DSA C++

if (node->left) q.push([1]);
if (node->right) q.push([2]);

Drag options to blanks, or click blank then click option'

Anode->left

Bnode->right

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing string literals instead of node pointers

Swapping left and right children

We must push the actual child nodes 'node->left' and 'node->right' into the queue.

4fill in blank

hard

Fill both blanks to correctly iterate over the current level size and pop nodes.

DSA C++

int size = q.[1]();
for (int i = 0; i < size; i++) {
    TreeNode* node = q.[2]();
    q.pop();
    // process node
}

Drag options to blanks, or click blank then click option'

Asize

Bfront

Cback

Dempty

Attempts:

3 left

💡 Hint

Common Mistakes

Using back() instead of front()

Using empty() instead of size()

Use q.size() to get current level size and q.front() to access the first node in the queue.

5fill in blank

hard

Fill all three blanks to complete the zigzag level order traversal function.

DSA C++

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> [1];
    if (!root) return [2];
    queue<TreeNode*> q;
    q.push(root);
    int level = 0;
    while (!q.empty()) {
        int size = q.size();
        vector<int> currentLevel;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        if (level % 2 == 1) {
            reverse(currentLevel.begin(), currentLevel.end());
        }
        [1].push_back(currentLevel);
        level++;
    }
    return [3];
}

Drag options to blanks, or click blank then click option'

Aresult

Blevels

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for declaration and return

Returning an uninitialized vector

The vector 'result' is declared, returned, and used to store levels.

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