हमारे पास 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