এই সমস্যায় রিকার্শন বা স্ট্যাক ব্যবহার না করে বাইনারি ট্রির পোস্টঅর্ডার ট্রাভার্সাল প্রিন্ট করতে হবে।
সংজ্ঞা
- বাইনারি ট্রি: প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড।
- পোস্টঅর্ডার ট্রাভার্সাল: বাম সাবট্রি → ডান সাবট্রি → রুট।
উদাহরণ
ট্রির পোস্টঅর্ডার: 8 4 2 7 9 6
পদ্ধতি ১: হ্যাশ টেবিল (visited সেট) ব্যবহার করে
ডেপথ-ফার্স্ট সার্চ বেসড টেকনিকসহ একটি unordered_set দিয়ে ভিজিট করা নোডগুলো ট্র্যাক করা হয়।
C++ প্রোগ্রাম (হ্যাশ টেবিল)
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
void postOrderTraversal(Node* head) {
Node* temp = head;
unordered_set<Node*> visited;
while (temp && visited.find(temp) == visited.end()) {
if (temp->left && visited.find(temp->left) == visited.end())
temp = temp->left;
else if (temp->right && visited.find(temp->right) == visited.end())
temp = temp->right;
else {
cout << temp->data << "\t";
visited.insert(temp);
temp = head;
}
}
}
Node* insertNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int main() {
Node* root = insertNode(6);
root->left = insertNode(2);
root->right = insertNode(9);
root->left->left = insertNode(8);
root->left->right = insertNode(4);
root->right->left = insertNode(7);
root->right->left->left = insertNode(13);
cout << "বাইনারি ট্রির পোস্ট অর্ডার ট্রাভার্সাল:\n";
postOrderTraversal(root);
return 0;
}
আউটপুট
বাইনারি ট্রির পোস্ট অর্ডার ট্রাভার্সাল: 8 4 2 13 7 9 6
পদ্ধতি ২: আনঅর্ডার্ড ম্যাপ (প্যারেন্ট ম্যাপ) ব্যবহার করে — আরও কার্যকর
ভিজিটেড ফ্ল্যাগের পরিবর্তে প্যারেন্ট ম্যাপ রাখা হয়, যা ট্র্যাকব্যাকের ওভারহেড কমায়।
C++ প্রোগ্রাম (আনঅর্ডার্ড ম্যাপ)
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
bool visited;
};
void postOrderTraversal(Node* root) {
Node* n = root;
unordered_map<Node*, Node*> postorder;
postorder.insert({root, nullptr});
while (n) {
if (n->left && postorder.find(n->left) == postorder.end()) {
postorder.insert({n->left, n});
n = n->left;
} else if (n->right && postorder.find(n->right) == postorder.end()) {
postorder.insert({n->right, n});
n = n->right;
} else {
cout << n->data << "\t";
n = postorder[n];
}
}
}
Node* insertNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
node->visited = false;
return node;
}
int main() {
Node* root = insertNode(6);
root->left = insertNode(2);
root->right = insertNode(9);
root->left->left = insertNode(8);
root->left->right = insertNode(4);
root->right->left = insertNode(7);
root->right->left->left = insertNode(13);
cout << "বাইনারি ট্রির পোস্ট অর্ডার ট্রাভার্সাল:\n";
postOrderTraversal(root);
return 0;
}
আউটপুট
বাইনারি ট্রির পোস্ট অর্ডার ট্রাভার্সাল: 8 4 2 13 7 9 6
