Zigzag Level Order Traversal in DSA C

Mental Model

We visit nodes level by level but alternate the direction of reading each level, left to right then right to left.

Analogy: Imagine reading lines of text on a page where the first line is read left to right, the next line right to left, then left to right again, like a zigzag pattern.

      1
     / \
    2   3
   / \   \
  4   5   6

Levels:
Level 0: 1 (left to right)
Level 1: 3 -> 2 (right to left)
Level 2: 4 -> 5 -> 6 (left to right)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3 -> 4, 5, 6 (as shown above)

Goal: Traverse the tree level by level, alternating direction each level, to get [[1], [3, 2], [4, 5, 6]]

Step 1: Start at root node 1, direction left to right

Level 0: [1] ↑ direction: left to right

Why: We begin traversal from the root, reading left to right on the first level

Step 2: Move to level 1 nodes 2 and 3, reverse direction to right to left

Level 1: [3, 2] ↑ direction: right to left

Why: Next level is read in opposite direction to create zigzag pattern

Step 3: Move to level 2 nodes 4, 5, 6, direction back to left to right

Level 2: [4, 5, 6] ↑ direction: left to right

Why: Alternate direction again for next level

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Definition for a binary tree node.
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Queue node for BFS
typedef struct QueueNode {
    TreeNode *node;
    struct QueueNode *next;
} QueueNode;

// Queue structure
typedef struct Queue {
    QueueNode *front;
    QueueNode *rear;
} Queue;

// Initialize queue
void initQueue(Queue *q) {
    q->front = NULL;
    q->rear = NULL;
}

// Check if queue is empty
int isEmpty(Queue *q) {
    return q->front == NULL;
}

// Enqueue
void enqueue(Queue *q, TreeNode *node) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// Dequeue
TreeNode *dequeue(Queue *q) {
    if (isEmpty(q)) return NULL;
    QueueNode *temp = q->front;
    TreeNode *node = temp->node;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return node;
}

// Create new tree node
TreeNode *newTreeNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Function to print array of values
void printLevel(int *arr, int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i != size - 1) printf(", ");
    }
    printf("]");
}

// Zigzag level order traversal
void zigzagLevelOrder(TreeNode *root) {
    if (root == NULL) return;
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    int leftToRight = 1; // direction flag

    printf("[");
    int firstLevel = 1;

    while (!isEmpty(&q)) {
        int levelSize = 0;
        QueueNode *temp = q.front;
        // Count nodes at current level
        while (temp != NULL) {
            levelSize++;
            temp = temp->next;
        }

        int *levelNodes = (int *)malloc(levelSize * sizeof(int));

        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = dequeue(&q);
            levelNodes[i] = node->val;
            if (node->left) enqueue(&q, node->left);
            if (node->right) enqueue(&q, node->right);
        }

        // Print level in zigzag order
        if (!firstLevel) printf(", ");
        printf("[");
        if (leftToRight) {
            for (int i = 0; i < levelSize; i++) {
                printf("%d", levelNodes[i]);
                if (i != levelSize - 1) printf(", ");
            }
        } else {
            for (int i = levelSize - 1; i >= 0; i--) {
                printf("%d", levelNodes[i]);
                if (i != 0) printf(", ");
            }
        }
        printf("]");

        free(levelNodes);
        leftToRight = !leftToRight; // switch direction
        firstLevel = 0;
    }
    printf("]\n");
}

int main() {
    // Build tree:
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    TreeNode *root = newTreeNode(1);
    root->left = newTreeNode(2);
    root->right = newTreeNode(3);
    root->left->left = newTreeNode(4);
    root->left->right = newTreeNode(5);
    root->right->right = newTreeNode(6);

    zigzagLevelOrder(root);
    return 0;
}

enqueue(&q, root);

start BFS with root node in queue

while (!isEmpty(&q)) {

process nodes level by level until queue is empty

while (temp != NULL) { levelSize++; temp = temp->next; }

count number of nodes at current level

for (int i = 0; i < levelSize; i++) { TreeNode *node = dequeue(&q); ... }

dequeue all nodes of current level and enqueue their children

if (leftToRight) { print left to right } else { print right to left }

print current level nodes in zigzag order

leftToRight = !leftToRight;

flip direction for next level

Output

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

Complexity Analysis

Time: O(n) because each node is visited exactly once during the traversal

Space: O(n) because the queue and level storage can hold up to all nodes at the widest level

vs Alternative: Compared to normal level order traversal, zigzag adds only a direction flip and reversed printing, so time complexity remains O(n) with minor extra space for reversing output

Edge Cases

Empty tree (root is NULL)

Function returns immediately without printing anything

DSA C

if (root == NULL) return;

Tree with single node

Prints single level with one node in normal order

DSA C

enqueue(&q, root);

Tree with only left or only right children

Traversal still works level by level, alternating direction even if levels have one node

DSA C

for (int i = 0; i < levelSize; i++) { TreeNode *node = dequeue(&q); ... }

When to Use This Pattern

When a problem asks for level order traversal but with alternating directions each level, use zigzag level order traversal to handle the direction flip cleanly.

Common Mistakes

Mistake: Not flipping the direction flag after each level, causing all levels to print in the same order
Fix: Toggle the direction flag (leftToRight = !leftToRight) after processing each level

Mistake: Printing nodes in the order they are dequeued without reversing on alternate levels
Fix: Reverse the order of printing for every other level to achieve zigzag pattern

Summary

It traverses a binary tree level by level, alternating the direction of node values printed at each level.

Use it when you need to visit nodes in a zigzag pattern instead of straight left-to-right level order.

The key insight is to flip the direction after each level and print nodes accordingly.

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