এই সমস্যাতে, আমাদের একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হলো বাইনারি ট্রিটিকে জিগজ্যাগ ফর্মে প্রিন্ট করা।
উদাহরণ:
উপরোক্ত বাইনারি ট্রির জিগজ্যাগ ট্রাভার্সাল:
3 5 1 8 7 0 4
এই সমস্যা সমাধান করতে, আমাদের বাইনারি ট্রি লেভেল বাই লেভেল ট্রাভার্স করতে হবে। প্রতিটি লেভেলের পরে ট্রাভার্সাল অর্ডার উল্টে যাবে।
আমরা দুটি স্ট্যাক (current এবং next) এবং অর্ডার জানানোর জন্য একটি বুলিয়ান ভেরিয়েবল ব্যবহার করব। প্রথমে current স্ট্যাক থেকে নোড ট্রাভার্স করব এবং লेफ্ট চাইল্ড থেকে রাইট চাইল্ড পর্যন্ত নোডগুলো next স্ট্যাকে পুশ করব যাতে রিভার্স অর্ডার পাওয়া যায়। আবার current স্ট্যাক থেকে রিভার্স করব। অর্ডার ভেরিয়েবলটি নির্ধারণ করবে কোন সাইড আগে প্রিন্ট হবে।
উদাহরণ
সমাধানের প্রোগ্রাম:
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
void zigZagTreeTraversal(struct Node* root) {
if (!root)
return;
stack currentLevel;
stack nextLevel;
currentLevel.push(root);
bool LtR = true;
while (!currentLevel.empty()) {
struct Node* temp = currentLevel.top();
currentLevel.pop();
if (temp) {
cout << temp->data << "\t";
if (LtR) {
if (temp->left)
nextLevel.push(temp->left);
if (temp->right)
nextLevel.push(temp->right);
} else {
if (temp->right)
nextLevel.push(temp->right);
if (temp->left)
nextLevel.push(temp->left);
}
}
if (currentLevel.empty()) {
LtR = !LtR;
swap(currentLevel, nextLevel);
}
}
}
struct Node* insertNode(int data) {
struct Node* node = new struct Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main() {
struct Node* root = insertNode(3);
root->left = insertNode(1);
root->right = insertNode(5);
root->left->left = insertNode(8);
root->left->right = insertNode(7);
root->right->left = insertNode(0);
root->right->right = insertNode(4);
cout << "ZigZag traversal of the given binary tree is \n";
zigZagTreeTraversal(root);
return 0;
} আউটপুট
ZigZag traversal of the given binary tree is 3 5 1 8 7 0 4
