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.