इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य ट्री का जिगजैग लेवल ऑर्डर ट्रैवर्सल प्रिंट करना है। इस ट्रैवर्सल के लिए हम केवल एक सिंगल क्यू का उपयोग करेंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,

आउटपुट -
3 1 7 2 8 9 5
सिंगल क्यू का उपयोग करके इस समस्या को हल करने के लिए, हम क्यू के साथ एक अतिरिक्त सेपरेशन फ्लैग और डायरेक्शन फ्लैग का उपयोग करेंगे।
अब, हम ट्री को लेवल दर लेवल ट्रैवर्स करेंगे, रूट एलिमेंट डालेंगे, अब क्यू के प्रत्येक एलिमेंट के लिए उसके चाइल्ड नोड को क्यू में डालेंगे। यदि NULL मिलता है, तो हम डायरेक्शन चेक करेंगे और फिर दिए गए डायरेक्शन में एलिमेंट्स को ट्रैवर्स करेंगे। फिर हम तब तक डालते रहेंगे जब तक हम अंतिम NULL पर नहीं पहुंच जाते।
उदाहरण
हमारे समाधान को दर्शाने वाला प्रोग्राम,
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* insertNode(int data) {
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
void zigZagTraversal(struct Node* root, int n) {
struct Node* queue[2 * n];
int top = -1;
int front = 1;
queue[++top] = NULL;
queue[++top] = root;
queue[++top] = NULL;
int prevFront = 0, count = 1;
while (1) {
struct Node* curr = queue[front];
if (curr == NULL) {
if (front == top)
break;
else {
if (count % 2 == 0) {
for (int i = prevFront + 1; i < front; i++)
cout << queue[i]->data << "\t";
} else {
for (int i = front - 1; i > prevFront; i--)
cout << queue[i]->data << "\t";
}
prevFront = front;
count++;
front++;
queue[++top] = NULL;
continue;
}
}
if (curr->left != NULL)
queue[++top] = curr->left;
if (curr->right != NULL)
queue[++top] = curr->right;
front++;
}
if (count % 2 == 0) {
for (int i = prevFront + 1; i < top; i++)
cout << queue[i]->data << "\t";
} else {
for (int i = top - 1; i > prevFront; i--)
cout << queue[i]->data << "\t";
}
}
int main() {
struct Node* root = insertNode(3);
root->left = insertNode(1);
root->right = insertNode(7);
root->left->left = insertNode(5);
root->left->right = insertNode(9);
root->right->left = insertNode(8);
root->right->right = insertNode(2);
cout << "ट्री का जिग जैग ट्रैवर्सल है :\n";
zigZagTraversal(root, 7);
return 0;
}
आउटपुट
ट्री का जिग जैग ट्रैवर्सल है : 3 1 7 2 8 9 5