Zigzag Level Order Traversal in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Level Order Traversal on a simple tree

What is the output of the following C++ code performing zigzag level order traversal on the given binary tree?

DSA C++

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

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    deque<TreeNode*> dq;
    dq.push_back(root);
    bool leftToRight = true;
    while (!dq.empty()) {
        int size = dq.size();
        vector<int> level(size);
        for (int i = 0; i < size; ++i) {
            TreeNode* node = dq.front();
            dq.pop_front();
            int index = leftToRight ? i : (size - 1 - i);
            level[index] = node->val;
            if (node->left) dq.push_back(node->left);
            if (node->right) dq.push_back(node->right);
        }
        leftToRight = !leftToRight;
        result.push_back(level);
    }
    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 (auto& level : res) {
        for (int val : level) cout << val << " ";
        cout << "\n";
    }
    return 0;
}

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

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

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

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

💡 Hint

Remember that zigzag means alternating the order of nodes at each level.

The traversal starts left to right at level 0, so output is [1].

At level 1, the order is right to left, so nodes 3 and 2 are reversed to [3, 2].

At level 2, order is left to right again, so nodes 4, 5, 6 are in normal order.

🧠 Conceptual

intermediate

Understanding the role of deque in zigzag traversal

Why is a double-ended queue (deque) used in zigzag level order traversal instead of a regular queue?

A Because deque prevents duplicate nodes from being added.

B Because deque automatically sorts the nodes at each level.

C Because deque uses less memory than a regular queue.

D Because deque allows insertion and deletion from both ends, enabling reversal of traversal direction efficiently.

💡 Hint

Think about how zigzag traversal changes direction at each level.

Zigzag traversal requires visiting nodes from left to right on one level and right to left on the next.

A deque allows adding and removing nodes from both ends, making it easy to switch traversal direction without extra reversing steps.

❓ Predict Output

advanced

Output of zigzag traversal with null children nodes

What is the output of the following zigzag traversal code on the given tree with some null children?

DSA C++

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

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    deque<TreeNode*> dq;
    dq.push_back(root);
    bool leftToRight = true;
    while (!dq.empty()) {
        int size = dq.size();
        vector<int> level(size);
        for (int i = 0; i < size; ++i) {
            TreeNode* node = dq.front();
            dq.pop_front();
            int index = leftToRight ? i : (size - 1 - i);
            level[index] = node->val;
            if (node->left) dq.push_back(node->left);
            if (node->right) dq.push_back(node->right);
        }
        leftToRight = !leftToRight;
        result.push_back(level);
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->left->right = new TreeNode(40);
    root->right->left = new TreeNode(50);

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

A [[10], [30, 20], [40, 50]]

B [[10], [20, 30], [50, 40]]

C [[10], [30, 20], [50, 40]]

D [[10], [20, 30], [40, 50]]

💡 Hint

Check the order of nodes at each level carefully, especially the last level.

Level 0: left to right → [10]

Level 1: right to left → [30, 20]

Level 2: left to right → children 40 and 50 in order [40, 50]

🔧 Debug

advanced

Identify the error in zigzag traversal code snippet

What error will the following code produce when performing zigzag level order traversal?

DSA C++

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    deque<TreeNode*> dq;
    dq.push_back(root);
    bool leftToRight = true;
    while (!dq.empty()) {
        int size = dq.size();
        vector<int> level(size);
        for (int i = 0; i < size; ++i) {
            TreeNode* node = dq.back();
            dq.pop_back();
            int index = leftToRight ? i : (size - 1 - i);
            level[index] = node->val;
            if (node->left) dq.push_front(node->left);
            if (node->right) dq.push_front(node->right);
        }
        leftToRight = !leftToRight;
        result.push_back(level);
    }
    return result;
}

A The code produces reversed output but no error.

B The code causes an infinite loop because nodes are added incorrectly.

C The code throws a runtime error due to accessing empty deque.

D The code runs correctly and returns the zigzag traversal.

💡 Hint

Check how nodes are added and removed from the deque inside the loop.

The code removes nodes from the back but adds children to the front in the same loop, causing the deque size to never reduce properly.

This leads to an infinite loop.

🚀 Application

expert

Number of nodes processed in zigzag traversal

Given a perfect binary tree of height 3 (levels 0 to 3), how many nodes will be processed in total during a zigzag level order traversal?

A 15

B 7

C 14

D 8

💡 Hint

Recall the total number of nodes in a perfect binary tree of height h is 2^(h+1) - 1.

A perfect binary tree of height 3 has 2^(3+1) - 1 = 15 nodes.

Zigzag traversal visits every node exactly once, so total processed nodes = 15.