আমাদের দুটি অ্যারে আছে BST-এর উপাদানগুলো প্রতিনিধিত্ব করতে। যদি আমরা উভয় অ্যারে থেকে বাম থেকে ডানে উপাদান নিয়ে BST ফর্ম করি, তবে উভয় সিকোয়েন্স একই BST তৈরি করবে কিনা তা যাচাই করতে হবে। কিন্তু স্ট্রিকশন হলো আমরা BST বানাতে পারব না। ধরুন দুটি অ্যারে {2, 4, 1, 3}, এবং {2, 1, 4, 3}, তবে আমরা দেখতে পাচ্ছি উভয় সিকোয়েন্স একই BST ফর্ম করতে পারে।
অ্যাপ্রোচটি সহজ। আমরা জানি, বাম সাবট্রির উপাদানগুলো রুট থেকে ছোট এবং ডান সাবট্রির উপাদানগুলো বড়। এই দুটি লিস্ট একই BST রিপ্রেজেন্ট করবে যদি প্রতিটি উপাদান x-এর জন্য, x-এর বাম ও ডান সাবট্রির উপাদানগুলো উভয় অ্যারেতেও তার পরে আসে। একই বৈশিষ্ট্য বাম ও ডান সাবট্রির রুটের জন্যও সত্য। আমরা চেক করব পরবর্তী ছোট এবং বড় উপাদানগুলো উভয় অ্যারেতে একই কিনা। এই একই প্রোপার্টি রিকার্সিভলি বাম ও ডান সাবট্রির জন্য চেক করা হবে।
উদাহরণ
#include <iostream> using namespace std; bool isSameCheckHelper(int tree1[], int tree2[], int n, int i1, int i2, int min, int max) { int j, k; for (j = i1; j < n; j++) if (tree1[j] > min && tree1[j] < max) break; for (k = i2; k < n; k++) if (tree2[k] > min && tree2[k] < max) break; if (j==n && k==n) //If the parent element is leaf in both arrays return true; if (((j==n)^(k==n)) || tree1[j]!=tree2[k]) return false; return isSameCheckHelper(tree1, tree2, n, j+1, k+1, tree1[j], max) && // for Right Subtree isSameCheckHelper(tree1, tree2, n, j+1, k+1, min, tree1[j]); // for Left Subtree } bool areBSTSame(int first[], int second[], int n) { return isSameCheckHelper(first, second, n, 0, 0, INT_MIN, INT_MAX); } int main() { int first[] = {8, 3, 6, 1, 4, 7, 10, 14, 13}; int second[] = {8, 10, 14, 3, 6, 4, 1, 7, 13}; int n=sizeof(first)/sizeof(first[0]); if(areBSTSame(first, second, n)) { cout << "Two BSTs are same"; } else { cout << "Two BSTs are not same"; } }আউটপুট
Two BSTs are same
