इस समस्या में, हमें एक बाइनरी ट्री BT दिया गया है। हमारा कार्य दिए गए बाइनरी ट्री में सबसे बड़ा BST उपट्री खोजना है।
बाइनरी ट्री डेटा स्टोरेज उद्देश्यों के लिए उपयोग की जाने वाली एक विशेष डेटा संरचना है। एक बाइनरी ट्री में एक विशेष शर्त होती है कि प्रत्येक नोड के अधिकतम दो बच्चे हो सकते हैं।
बाइनरी सर्च ट्री (BST) एक ट्री है जिसमें सभी नोड्स नीचे उल्लिखित गुणों का पालन करते हैं −
बाएं उप-ट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से कम होता है।
दाएं उप-ट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से अधिक या बराबर होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :
आउटपुट : 3
व्याख्या
पूर्ण बाइनरी ट्री एक BST है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान ट्री का इन-ऑर्डर ट्रैवर्सल करना है। और ट्री के प्रत्येक नोड के लिए, जांचें कि इसके उपट्री BST हैं या नहीं। अंत में सबसे बड़े उपट्री का आकार लौटाएं जो BST है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include<bits/stdc++.h> using namespace std; class node{ public: int data; node* left; node* right; node(int data){ this->data = data; this->left = NULL; this->right = NULL; } }; int findTreeSize(node* node) { if (node == NULL) return 0; else return(findTreeSize(node->left) + findTreeSize(node->right) + 1); } int isBSTree(struct node* node) { if (node == NULL) return 1; if (node->left != NULL && node->left->data > node->data) return 0; if (node->right != NULL && node->right->data < node->data) return 0; if (!isBSTree(node->left) || !isBSTree(node->right)) return 0; return 1; } int findlargestBSTSize(struct node *root) { if (isBSTree(root)){ return findTreeSize(root); } else return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right)); } int main() { node *root = new node(5); root->left = new node(2); root->right = new node(8); root->left->left = new node(1); root->left->right = new node(4); cout<<"सबसे बड़े संभावित BST का आकार है "<<findlargestBSTSize(root); return 0; } आउटपुट
सबसे बड़े संभावित BST का आकार है 5
एक अन्य दृष्टिकोण
समस्या का एक अन्य समाधान ट्री को नीचे से पार करना और इसके चाइल्ड नोड्स का उपयोग करके जांचना है कि यह BST है या नहीं। इसके लिए नोड के लिए, हम ट्रैक रखेंगे
यदि यह BST है या नहीं।
बाएं उप-ट्री के मामले में अधिकतम तत्व का मान।
दाएं उप-ट्री के मामले में न्यूनतम तत्व। इन मानों की तुलना वर्तमान नोड से BST की जांच के लिए करने की आवश्यकता है।
साथ ही, सबसे बड़े BST का आकार वर्तमान BST आकार के साथ जांच करके अपडेट किया जाएगा।
उदाहरण
#include<bits/stdc++.h> using namespace std; class node{ public: int data; node* left; node* right; node(int data){ this->data = data; this->left = NULL; this->right = NULL; } }; int findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) { if (node == NULL){ *isBSTree = true; return 0; } int min = INT_MAX; bool left_flag = false; bool right_flag = false; int leftSubtreeSize,rightSubTreeSize; *maxValLsubTree = INT_MIN; leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree); if (*isBSTree == true && node->data > *maxValLsubTree) left_flag = true; min = *minValRsubTree; *minValRsubTree = INT_MAX; rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree); if (*isBSTree == true && node->data < *minValRsubTree) right_flag = true; if (min < *minValRsubTree) *minValRsubTree = min; if (node->data < *minValRsubTree) *minValRsubTree = node->data; if (node->data > *maxValLsubTree) *maxValLsubTree = node->data; if(left_flag && right_flag){ if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize) *maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1); return (leftSubtreeSize + rightSubTreeSize + 1); } else{ *isBSTree = false; return 0; } } int findlargestBSTSize(node* node){ int min = INT_MAX; int max = INT_MIN; int largestBSTSize = 0; bool isBST = false; findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST); return largestBSTSize; } int main(){ node *root = new node(5); root->left = new node(2); root->right = new node(8); root->left->left = new node(1); root->left->right = new node(4); cout<<"सबसे बड़े BST का आकार है "<<findlargestBSTSize(root); return 0; } आउटपुट
सबसे बड़े BST का आकार है 5
