ধরুন আমাদের একটি অ্যারেতে উপাদানগুলির একটি তালিকা আছে, আমাদের পরীক্ষা করতে হবে, উপাদানগুলি একটি বাইনারি অনুসন্ধান গাছের প্রি-অর্ডার ট্রাভার্সাল হতে পারে কি না। ধরুন একটি ক্রম হল {40, 30, 35, 80, 100}, তাহলে গাছটি হবে −
আমরা একটি স্ট্যাক ব্যবহার করে এটি সমাধান করতে পারি। এই সমস্যা সমাধানের জন্য আমাদের এই পদক্ষেপগুলি অনুসরণ করতে হবে৷
- খালি স্ট্যাক সংজ্ঞায়িত করুন
- মূলকে ঋণাত্মক অসীম হিসাবে সেট করুন
- প্রি-অর্ডার অনুক্রমের প্রতিটি উপাদানের জন্য, নিম্নলিখিতগুলি করুন −
- যদি উপাদানটি বর্তমান রুটের চেয়ে ছোট হয়, তাহলে মিথ্যা ফেরত দিন
- স্ট্যাক টপ থেকে এলিমেন্ট বড় থাকাকালীন স্ট্যাক থেকে এলিমেন্ট মুছে ফেলতে থাকুন, এবং সবশেষে সরানো এলিমেন্টটিকে রুট হিসেবে তৈরি করুন।
- উপাদানটিকে স্ট্যাকের মধ্যে পুশ করুন
উদাহরণ
#include <iostream>
#include <stack>
using namespace std;
bool isValidPreorder(int pre[], int n) {
stack<int> stk;
int root = INT_MIN;
for (int i=0; i<n; i++) {
if (pre[i] < root)
return false;
while (!stk.empty() && stk.top()<pre[i]) {
root = stk.top();
stk.pop();
}
stk.push(pre[i]);
}
return true;
}
int main() {
int pre[] = {40, 30, 35, 80, 100};
int n = sizeof(pre)/sizeof(pre[0]);
if(isValidPreorder(pre, n))
cout << "This can form BST";
else
cout << "This can not form BST";
} আউটপুট
This can form BST
