Zigzag Level Order Traversal in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue for BFS traversal.

DSA C

Queue* queue = [1]();

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

AstartArray

BinitStack

CnewList

DcreateQueue

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack initialization instead of queue.

Using list or array initialization which is not suitable here.

We need to create a queue to perform BFS. The function createQueue initializes it.

2fill in blank

medium

Complete the code to check if the queue is empty during traversal.

DSA C

while (![1](queue)) {

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

AisEmpty

BisFull

CisNull

DisReady

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if queue is full instead of empty.

Using incorrect function names.

We continue traversal while the queue is not empty, so we check with isEmpty.

3fill in blank

hard

Fix the error in the code to correctly pop the front node from the queue.

DSA C

TreeNode* node = [1](queue);

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

Adequeue

BpopStack

CremoveLast

DpeekFront

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack pop instead of queue dequeue.

Using peek which does not remove the element.

To remove and get the front element from the queue, we use dequeue.

4fill in blank

hard

Fill both blanks to correctly reverse the order of nodes at odd levels.

DSA C

if (level % 2 == 1) {
    reverseArray([1], [2]);
}

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

AcurrentLevelNodes

BnodeCount

ClevelNodes

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable names for array or size.

Reversing at even levels instead of odd.

We reverse the array currentLevelNodes of length nodeCount at odd levels.

5fill in blank

hard

Fill all three blanks to correctly add child nodes to the queue during traversal.

DSA C

if (node->left != NULL) {
    [1](queue, node->[2]);
}
if (node->right != NULL) {
    [3](queue, node->right);
}

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

Aenqueue

Bleft

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using push instead of enqueue for queue.

Accessing wrong child pointers.

We enqueue left and right child nodes to the queue for BFS traversal.

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