আমাদের একটি অ্যারে A আছে, আমাদের যাচাই করতে হবে অ্যারেটি n লেভেলের একটি BST কিনা তা প্রতিনিধিত্ব করতে পারে কিনা। যেহেতু লেভেল n, আমরা নিচের মত করে ট্রি কনস্ট্রাক্ট করতে পারি। ধরা যাক একটি সংখ্যা k, k-এর চেয়ে বড় মান ডান পাশে যাবে, এবং ছোট মান বাম পাশে। ধরুন দুটি লিস্ট আছে: {50, 20, 9, 25, 10}, এবং {50, 30, 20, 25, 10}
প্রথমটি বৈধ নয়, কিন্তু দ্বিতীয়টি বৈধ।
এটি যাচাই করার দুটি পদ্ধতি আছে: BST তৈরি করে হাইট চেক করা, অথবা অ্যারে-ভিত্তিক পদ্ধতি। অ্যারে-ভিত্তিক পদ্ধতিটি নিচে:
- দুটি ভেরিয়েবল নিন: max = infinity (বাম সাবট্রির সর্বোচ্চ সীমা চিহ্নিত করতে), এবং min = negative infinity (ডান সাবট্রির ন্যূনতম সীমা চিহ্নিত করতে)।
- প্রতিটি উপাদান arr[i] থেকে arr[n-1] পর্যন্ত নিচের ধাপগুলো করুন:
- যদি arr[i] > arr[i-1] এবং arr[i] > min এবং arr[i] < max, তবে min := arr[i-1] আপডেট করুন।
- অন্যথায় যদি arr[i] > min এবং arr[i] < max, তবে max := arr[i] আপডেট করুন।
- যদি 上記 দুটি শর্তই বৈধ না হয়, তবে উপাদানটি নতুন লেভেলে ইনসার্ট হবে, তাই ব্রেক করুন।
উদাহরণ
#include <iostream> using namespace std; bool canMakeBSTifHeightN(int arr[], int n) { int min = INT_MIN; int max = INT_MAX; for(int i = 1; i < n; i++){ if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) { min = arr[i - 1]; } else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) { max = arr[i - 1]; } else { return true; } } return false; } int main() { int elements[] = {50, 30, 20, 25, 10}; int n = sizeof(elements)/sizeof(elements[0]); if (canMakeBSTifHeightN(elements, n)) cout << "We can make BST of height " << n; else cout << "We can not make BST of height " << n; }আউটপুট
We can make BST of height 5
