এই সমস্যাতে, আমাদের একটি অ্যারে preOrder[] দেওয়া আছে যা বাইনারি সার্চ ট্রি (BST)-র প্রি-অর্ডার ট্রাভার্সালকে রিপ্রেজেন্ট করে। আমাদের কাজ হলো প্রি-অর্ডার ট্রাভার্সাল থেকে বিএসটির পোস্ট-অর্ডার ট্রাভার্সাল বের করা।
উদাহরণ দিয়ে সমস্যা বোঝা যাক,
ইনপুট
preOrder[] = {5, 2, 4, 7, 12}
আউটপুট
{4, 2, 12, 7, 5}
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হলো দেওয়া প্রি-অর্ডার ট্রাভার্সাল থেকে একটি বিএসটি (BST) তৈরি করা। এবং তারপর ট্রির পোস্ট-অর্ডার ট্রাভার্সাল করা। এই সমাধানটি ঠিক আছে কিন্তু একটি আরও কার্যকর সমাধান হলো:
আমরা প্রি-অর্ডার অ্যারেটি একটি লিমিট (limit) দিয়ে ট্রাভার্স করব যাতে বাম ও ডান সাবট্রির (subtree) মানগুলো আলাদা করা যায়।
ট্রাভার্সালের ক্রম:
preOrder: Root -> Left -> Right postOrder: Left -> Right -> Root
প্রি-অর্ডারের প্রথম উপাদান যা রুট (root)। এর জন্য লিমিট {INT_MIN, Root}। তারপর প্রি-অর্ডার অ্যারেটি ট্রাভার্স করে লিমিটের মধ্যে থাকা সব উপাদানকে লিমিটের শেষ মানের সাথে সোয়াপ করব। একইভাবে ডান সাবট্রির জন্য করব এবং শেষে রুটটি যোগ করব।
সমাধান কোড (রিকার্সিভ):
উদাহরণ
#include <iostream>
using namespace std;
void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int upperLimit, int& index){
if (index == n)
return;
if (pre[index] < lowerLimit || pre[index] > upperLimit)
return;
int currNode = pre[index];
index++;
findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index);
findPostOrderTraversalRec(pre, n, currNode, upperLimit, index);
cout<<currNode<<" ";
}
void findPostOrderTraversalFromPreOrder(int pre[], int n){
int index = 0;
findPostOrderTraversalRec(pre, n, -1000, 1000, index);
}
int main(){
int pre[] = { 5, 2, 4, 7, 12 };
int n = sizeof(pre) / sizeof(pre[0]);
cout<<"PreOrder Traversal : \t";
for(int i = 0; i < n; i++)
cout<<pre[i]<<" ";
cout<<endl<<"Post Order Traversal : \t";
findPostOrderTraversalFromPreOrder(pre, n);
return 0;
}
আউটপুট
PreOrder Traversal − 5 2 4 7 12 Post Order Traversal − 4 2 12 7 5
এই সমস্যা সমাধানের আরেকটি পদ্ধতি হলো ইটারেটিভ (iterative) মেথড। যেহেতু প্রি-অর্ডার হলো রুট -> বাম -> ডান এবং পোস্ট-অর্ডার হলো বাম -> ডান -> রুট। এটি একটি লুপ এবং পিভট (pivot) এলিমেন্ট বের করে ক্যালকুলেট করা যায়। পিভট হলো যেখানে বাম সাবট্রির শেষ উপাদানটি থাকে। পিভট বের করা হয় রুট থেকে বড় প্রথম উপাদানের ইনডেক্স বের করে। এরপর বাম পার্টটি প্রথমে, তারপর ডান পার্টটি, এবং শেষে রুট প্রিন্ট করা হয়।
সমাধান কোড (ইটারেটিভ):
উদাহরণ
#include <iostream>
using namespace std;
void findPostOrderTraversalFromPreOrder(int pre[], int n){
int pivot = 0;
for(int i = 1; i < n; i++){
if (pre[0] <= pre[i]) {
pivot = i;
break;
}
}
for(int i = pivot - 1; i > 0; i--){
cout << pre[i] << " ";
}
for(int i = n - 1; i >= pivot; i--) {
cout << pre[i] << " ";
}
cout << pre[0];
}
int main(){
int pre[] = { 5, 2, 4, 7, 12 };
int n = sizeof(pre) / sizeof(pre[0]);
cout<<"PreOrder Traversal : \t";
for(int i = 0; i < n; i++)
cout<<pre[i]<<" ";
cout<<endl<<"Post Order Traversal : \t";
findPostOrderTraversalFromPreOrder(pre, n);
return 0;
}
আউটপুট
PreOrder Traversal − 5 2 4 7 12 Post Order Traversal − 4 2 12 7 5
