इस समस्या में हमें एक बाइनरी ट्री BT दिया जाता है। हमारा काम है किसी दिए गए बाइनरी ट्री में सबसे बड़ा BST सबट्री ढूंढना ।
बाइनरी ट्री एक विशेष डेटा संरचना है जिसका उपयोग डेटा भंडारण उद्देश्यों के लिए किया जाता है। बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं।
बाइनरी सर्च ट्री (बीएसटी) एक ऐसा पेड़ है जिसमें सभी नोड्स नीचे बताए गए गुणों का पालन करते हैं -
-
बाएँ उप-वृक्ष की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से कम है।
-
दाएँ उपट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से अधिक या उसके बराबर होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :
आउटपुट :3
स्पष्टीकरण
Full binary tree is a 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<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
return 0;
} आउटपुट
The size of the largest possible BST is 5
एक और तरीका
समस्या का एक अन्य समाधान पेड़ को नीचे से पार करना और यह जांचना है कि क्या यह अपने बच्चे के नोड्स का उपयोग करके बीएसटी है। इस नोड के लिए, हम ट्रैक करेंगे
अगर यह बीएसटी है या नहीं।
-
बाएँ सबट्री के मामले में अधिकतम तत्व का मान।
-
सही सबट्री के मामले में न्यूनतम तत्व। 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<<"The Size of the largest BST is "<<findlargestBSTSize(root);
return 0;
} आउटपुट
The Size of the largest BST is 5