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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Traversal on a Balanced Tree

What is the output of the zigzag level order traversal for the following binary tree?

Tree structure:
1
/ \
2 3
/ \ / \
4 5 6 7

DSA C

/*
Zigzag traversal visits nodes level by level.
Odd levels left to right, even levels right to left.
*/

// Expected output format: [[1], [3, 2], [4, 5, 6, 7]]

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

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

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

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

💡 Hint

Remember zigzag means alternate direction each level.

Level 1: left to right → [1]
Level 2: right to left → [3, 2]
Level 3: left to right → [4, 5, 6, 7]

🧠 Conceptual

intermediate

Understanding Zigzag Traversal Direction

In zigzag level order traversal, what determines the direction of traversal at each level?

A The height of the tree

B The number of nodes at the current level

C The values of the nodes at the current level

D The parity (odd/even) of the current level number

💡 Hint

Think about how the traversal alternates direction.

Zigzag traversal alternates direction based on whether the level number is odd or even.

🔧 Debug

advanced

Identify the Error in Zigzag Traversal Code

What error will this C code snippet cause when performing zigzag level order traversal? ```c if (level % 2 == 0) { // traverse left to right for (int i = 0; i < size; i++) { printf("%d ", queue[i]->val); } } else { // traverse right to left for (int i = size - 1; i >= 0; i--) { printf("%d ", queue[i]->val); } } ``` Assume level starts at 1 for root level.

DSA C

/* level starts at 1 */

A The traversal direction is reversed because level parity check is incorrect

B No error, code works correctly

C Runtime error due to invalid queue indexing

D Syntax error due to missing semicolon

💡 Hint

Check how parity relates to direction and level numbering.

If level starts at 1, even levels should be right to left, but code does left to right on even levels, reversing directions.

🚀 Application

advanced

Zigzag Traversal Output for Unbalanced Tree

Given this unbalanced binary tree:

10
/ \
5 15
\ \
7 20
/
17

What is the zigzag level order traversal output?

A [[10], [5, 15], [20, 7], [17]]

B [[10], [5, 15], [7, 20], [17]]

C [[10], [15, 5], [7, 20], [17]]

D [[10], [15, 5], [20, 7], [17]]

💡 Hint

Remember to alternate direction each level.

Level 1: left to right → [10]
Level 2: right to left → [15, 5]
Level 3: left to right → [7, 20]
Level 4: right to left → [17]

❓ Predict Output

expert

Output of Zigzag Traversal with Null Nodes Included

Consider this C code snippet that attempts zigzag traversal but includes NULL nodes in the queue: ```c // queue contains nodes including NULLs for (int i = 0; i < size; i++) { if (queue[i] != NULL) { printf("%d ", queue[i]->val); } else { printf("null "); } } ``` If the queue at a level is [node(1), NULL, node(3)], what is the printed output?

A 1 null 3

B 1 3

C null 1 3

D 1 null null 3

💡 Hint

Check how NULL nodes are handled in the print loop.

The code prints 'null ' for NULL nodes and the value for non-NULL nodes, so output is '1 null 3 '.

Practice

1. What does the Zigzag Level Order Traversal of a binary tree do differently compared to a normal level order traversal?

easy

A. It traverses the tree in preorder fashion.

B. It visits nodes only at even levels.

C. It visits nodes in reverse order of their insertion.

D. It alternates the direction of traversal at each level, left to right then right to left.

Solution

1. Step 1: Understand normal level order traversal

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

2. Step 2: Identify zigzag difference

   Zigzag traversal changes direction at each level, so first level left to right, next right to left, and so on.

3. Final Answer:

   It alternates the direction of traversal at each level, left to right then right to left. -> Option D

4. Quick Check:

   Zigzag alternates direction = It alternates the direction of traversal at each level, left to right then right to left. [OK]

Hint: Remember zigzag flips direction each level [OK]

Common Mistakes:

• Thinking it only visits even levels
• Confusing with preorder traversal
• Assuming it visits nodes in insertion order

2. Which of the following C code snippets correctly initializes a queue for level order traversal in Zigzag Level Order Traversal?

easy

A. Queue q; q.front = 0; q.rear = 0;

B. Queue* q = createQueue(); q->front = q->rear = -1;

C. Queue* q; q->front = 0; q->rear = 0;

D. Queue q = NULL; q->front = -1; q->rear = -1;

Solution

1. Step 1: Understand queue initialization in C

   Queue pointer must be assigned memory using createQueue() or malloc before accessing members.

2. Step 2: Check each option

   Queue* q = createQueue(); q->front = q->rear = -1; correctly creates a queue pointer and initializes front and rear to -1. Queue q; q.front = 0; q.rear = 0; uses struct without pointer but does not allocate memory. Queue* q; q->front = 0; q->rear = 0; uses pointer without allocation. Queue q = NULL; q->front = -1; q->rear = -1; assigns NULL to struct variable which is invalid.

3. Final Answer:

   Queue* q = createQueue(); q->front = q->rear = -1; -> Option B

4. Quick Check:

   Proper queue pointer initialization = Queue* q = createQueue(); q->front = q->rear = -1; [OK]

Hint: Allocate memory before using pointer members [OK]

Common Mistakes:

• Using uninitialized pointers
• Assigning NULL to struct variable
• Not allocating memory before access

3. Given the binary tree:

    1
   / \
  2   3
 / \   \
4   5   6

What is the output of Zigzag Level Order Traversal?

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. Right to left means [3, 2].

3. Step 3: Traverse level 2 left to right

   Level 2 nodes are 4, 5, 6. Left to right means [4, 5, 6].

4. Final Answer:

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

5. Quick Check:

   Zigzag order matches [[1], [3, 2], [4, 5, 6]] [OK]

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

Common Mistakes:

• Not reversing order on alternate levels
• Mixing node values order
• Confusing left and right children

4. Consider this snippet for Zigzag Level Order Traversal in C:

while (!isEmpty(queue)) {
    int size = queueSize(queue);
    for (int i = 0; i < size; i++) {
        Node* node = dequeue(queue);
        if (leftToRight) {
            addToResult(node->val);
        } else {
            addToResultAtFront(node->val);
        }
        if (node->left) enqueue(queue, node->left);
        if (node->right) enqueue(queue, node->right);
    }
    leftToRight = !leftToRight;
}

What is the main bug in this code?

medium

A. The for loop should run until queue is empty, not fixed size.

B. leftToRight flag is not toggled correctly.

C. Using addToResultAtFront causes inefficient insertion, should use a stack.

D. Nodes are enqueued after processing, should enqueue before.

Solution

1. Step 1: Analyze insertion method for zigzag

   Adding elements at front of a list repeatedly is inefficient; a stack or deque is better for reversing order.

2. Step 2: Check other parts

   leftToRight toggling is correct. Enqueuing children after processing is standard. For loop running fixed size is correct to process current level only.

3. Final Answer:

   Using addToResultAtFront causes inefficient insertion, should use a stack. -> Option C

4. Quick Check:

   Efficient reversal needs stack/deque, not front insertion [OK]

Hint: Use stack or deque for reverse order insertion [OK]

Common Mistakes:

• Not toggling direction flag
• Enqueuing nodes before processing
• Incorrect loop bounds for level size

5. You want to perform Zigzag Level Order Traversal on a binary tree but only print nodes at odd levels (1, 3, 5, ...). Which modification is correct?

hard

A. Add a level counter and print results only when level % 2 == 1.

B. Skip enqueuing nodes at even levels.

C. Toggle leftToRight only on odd levels.

D. Reverse the entire traversal output after completion.

Solution

1. Step 1: Track current level number

   Maintain a counter for levels starting at 1 for root level.

2. Step 2: Print only odd levels

   When processing each level, print or store nodes only if level number is odd (level % 2 == 1).

3. Step 3: Keep traversal logic unchanged

   Enqueue all children normally and toggle direction each level to maintain zigzag pattern.

4. Final Answer:

   Add a level counter and print results only when level % 2 == 1. -> Option A

5. Quick Check:

   Filter output by odd levels using counter [OK]

Hint: Use level counter and print only odd levels [OK]

Common Mistakes:

• Skipping enqueuing nodes breaks traversal
• Toggling direction only on odd levels breaks zigzag
• Reversing output after traversal is incorrect