Zigzag Level Order Traversal in DSA C++

Mental Model

We visit nodes level by level but alternate the direction of visiting each level, first left to right, then right to left, and so on.

Analogy: Imagine reading lines of text on a page: the first line left to right, the second line right to left, zigzagging your eyes as you go down.

       1
      / \
     2   3
    / \   \
   4   5   6

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, null, 6 (as shown above)

Goal: Print nodes level by level, alternating direction each level

Step 1: Start at root level (level 0), direction left to right

Level 0: [1] -> null

Why: We begin traversal from the root node left to right

Step 2: Collect children of level 0 nodes for level 1

Level 1 nodes: 2 -> 3 -> null

Why: Next level nodes are children of current level nodes

Step 3: Traverse level 1 nodes right to left

Level 1: 3 -> 2 -> null

Why: We alternate direction each level to create zigzag

Step 4: Collect children of level 1 nodes for level 2

Level 2 nodes: 4 -> 5 -> 6 -> null

Why: Gather next level nodes from children of level 1

Step 5: Traverse level 2 nodes left to right

Level 2: 4 -> 5 -> 6 -> null

Why: Direction alternates back to left to right

Result:

1 -> null
3 -> 2 -> null
4 -> 5 -> 6 -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;

    while (!q.empty()) {
        int size = q.size();
        vector<int> level(size);
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            int index = leftToRight ? i : (size - 1 - i);
            level[index] = node->val;  // place value based on direction

            if (node->left) q.push(node->left);  // add left child
            if (node->right) q.push(node->right); // add right child
        }
        result.push_back(level);  // add current level to result
        leftToRight = !leftToRight;  // flip direction
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    vector<vector<int>> res = zigzagLevelOrder(root);
    for (const auto& level : res) {
        for (int val : level) {
            cout << val << " ";
        }
        cout << "\n";
    }
    return 0;
}

queue<TreeNode*> q; q.push(root);

initialize queue with root to start level order traversal

while (!q.empty()) {

process nodes level by level until no nodes left

int size = q.size(); vector<int> level(size);

prepare container for current level values

TreeNode* node = q.front(); q.pop();

remove front node from queue to process it

int index = leftToRight ? i : (size - 1 - i); level[index] = node->val;

place node value in level vector according to current direction

if (node->left) q.push(node->left); if (node->right) q.push(node->right);

add children of current node to queue for next level

result.push_back(level); leftToRight = !leftToRight;

store current level and 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 we store all nodes in the queue and the result structure

vs Alternative: Compared to normal level order traversal, zigzag adds only a small overhead for reversing order, still O(n) overall

Edge Cases

Empty tree (root is null)

Returns empty result without processing

DSA C++

if (!root) return result;

Tree with only one node

Returns a single level with that node's value

DSA C++

queue<TreeNode*> q;
q.push(root);

Tree with uneven levels (some nodes missing children)

Processes existing nodes correctly, skipping null children

DSA C++

if (node->left) q.push(node->left);
if (node->right) q.push(node->right);

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 be traversed in the same order
Fix: Toggle the direction boolean after processing each level: leftToRight = !leftToRight;

Mistake: Appending nodes in order without placing them at correct indices for right-to-left levels
Fix: Use index calculation: index = leftToRight ? i : (size - 1 - i) to place values correctly

Summary

It prints the nodes of a binary tree level by level, alternating between left-to-right and right-to-left order.

Use it when you need to traverse a tree in a zigzag pattern to capture alternating directions per level.

The key insight is to use a direction flag and place node values in a temporary array at indices that reflect the current direction.

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