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