Zigzag Level Order Traversal in DSA C - Time & Space Complexity

Time Complexity: Zigzag Level Order Traversal

O(n)

Understanding Time Complexity

We want to understand how the time needed to traverse a tree in zigzag order changes as the tree grows.

How does the number of nodes affect the work done to visit them in this special order?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Zigzag level order traversal of a binary tree
void zigzagTraversal(TreeNode* root) {
    if (!root) return;
    std::deque dq;
    dq.push_back(root);
    bool leftToRight = true;
    while (!dq.empty()) {
        int size = dq.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = leftToRight ? dq.front() : dq.back();
            if (leftToRight) dq.pop_front(); else dq.pop_back();
            // process node->val here
            if (leftToRight) {
                if (node->left) dq.push_back(node->left);
                if (node->right) dq.push_back(node->right);
            } else {
                if (node->right) dq.push_front(node->right);
                if (node->left) dq.push_front(node->left);
            }
        }
        leftToRight = !leftToRight;
    }
}
    

This code visits all nodes in a binary tree level by level, alternating direction each level.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once in the while loop and inner for loop.
• How many times: Exactly once per node, since each node is added and removed from the deque once.

How Execution Grows With Input

As the number of nodes (n) grows, the code visits each node once, so operations grow roughly in direct proportion to n.

Input Size (n)	Approx. Operations
10	About 10 visits and deque operations
100	About 100 visits and deque operations
1000	About 1000 visits and deque operations

Pattern observation: Operations increase linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the traversal grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because of the zigzag and deque operations, the traversal takes more than linear time, maybe quadratic."

[OK] Correct: Each node is still visited once, and deque operations are constant time, so total work is proportional to the number of nodes.

Interview Connect

Understanding this traversal's time complexity shows you can analyze how data structure choices affect performance in tree algorithms.

Self-Check

"What if we used a simple queue instead of a deque and reversed the order of nodes after each level? How would the time complexity change?"

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