মনে করুন একটি অ্যারেতে এলিমেন্টের একটি লিস্ট আছে। আমাদের চেক করতে হবে এলিমেন্টগুলো কি বাইনারি সার্চ ট্রির প্রি-অর্ডার ট্রাভার্সাল হতে পারে। ধরুন একটি সিকোয়েন্স: {40, 30, 35, 80, 100}, তবে ট্রিটি হবে নিচের মতো:
এটি স্ট্যাক ব্যবহার করে সমাধান করা যায়। ধাপগুলো:
- খালি স্ট্যাক ডিফাইন করুন
- root কে নেগেটিভ ইনফিনিটিতে সেট করুন
- প্রি-অর্ডার সিকোয়েন্সের প্রতিটি এলিমেন্টের জন্য নিচের কাজ করুন:
- যদি এলিমেন্ট বর্তমান রুট থেকে ছোট হয়, false রিটার্ন করুন
- স্ট্যাক থেকে এলিমেন্ট পপ করুন যতক্ষণ না এলিমেন্ট স্ট্যাক টপ থেকে বড় হয়, এবং লাস্ট পপ করা এলিমেন্টকে রুট বানান
- এলিমেন্টকে স্ট্যাকে পুশ করুন
উদাহরণ কোড
#include <iostream>
#include <stack>
#include <climits>
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";
return 0;
}
আউটপুট
This can form BST
