एक बाइनरी ट्री में, प्रत्येक चाइल्ड नोड में केवल दो नोड (बाएं और दाएं) होते हैं। वृक्ष संरचनाएं केवल डेटा का प्रतिनिधित्व करती हैं। बाइनरी सर्च ट्री (बीएसटी) विशेष प्रकार के बाइनरी ट्री हैं जो इन शर्तों को पूरा करते हैं -
-
अपने पैरेंट की तुलना में, लेफ्ट चाइल्ड नोड छोटा होता है
-
दाहिने बच्चे का पैरेंट नोड चाइल्ड नोड से बड़ा होता है
मान लीजिए हमें एक बाइनरी ट्री दिया गया है, और हमें यह पता लगाना है कि इसमें सबसे बड़ा बाइनरी सर्च ट्री (BST) क्या है।
इस कार्य में, हम एक बाइनरी ट्री में सबसे बड़ा BST खोजने के लिए एक फ़ंक्शन बनाएंगे। जब बाइनरी ट्री अपने आप में एक BST होता है, तो पूरे बाइनरी ट्री का आकार निर्धारित करना संभव होता है। उदाहरण के तौर पर -
इनपुट
10 /\ 5 15 /\ \ 1 8 7
जैसा कि दिखाया गया है, इस मामले में हाइलाइट किया गया बीएसटी सबट्री सबसे बड़ा है। '3' सबट्री का आकार है, इसलिए रिटर्न वैल्यू सबट्री का आकार है।
इनपुट
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
आउटपुट
5
नोड्स वाले सबट्रीज़ जिनकी लंबाई उनके पैरेंट नोड्स की लंबाई से कम होती है, उनमें अधिकतम तीन आकार के BST नोड्स होते हैं।
दिए गए बाइनरी ट्री में सबसे बड़े BST का पता लगाने के लिए दृष्टिकोण
प्रत्येक नोड x के लिए, यदि निम्न बिंदु मान्य हैं, तो एक बाइनरी ट्री BST है। केवल वे नोड जिनका डेटा उनके मूल नोड से कम है, एक नोड के बाएँ उपप्रकार में दिखाई देते हैं। केवल एक नोड हो सकता है जिसमें उसके मूल नोड से अधिक डेटा हो। बाएँ और दाएँ दोनों उपप्रकारों को बाइनरी सर्च ट्री (BST) द्वारा विशेषता दी जानी चाहिए।
एल्गोरिदम होगा -
हम बाइनरी ट्री की जड़ से शुरू करेंगे और रिकर्सन का उपयोग करके इन-ऑर्डर ट्रैवर्सल करेंगे। वर्तमान नोड 'रूट' के लिए, हम निम्नलिखित कार्य करेंगे-
-
यदि यह एक मान्य BST का मूल है, तो हम इसका आकार वापस कर देते हैं।
-
नहीं तो, हम बाएँ और दाएँ सबट्री में सबसे बड़ा BST पाएंगे।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *
newNode (int data) {
struct Node *node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
struct Detail {
int size;
int max;
int min;
int ans;
bool isBST;
};
bool isBST (Node * root, int min, int max) {
if (root == NULL) {
return true;
}
if (root->data < min || root->data > max) {
return false;
}
return isBST (root->left, min, root->data - 1) &&
isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
if (root == NULL) {
return 0;
}
return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
// Current Subtree is BST.
if (isBST (root, INT_MIN, INT_MAX) == true) {
return size (root);
}
// Find largest BST in left and right subtrees.
return max (largestBST (root->left), largestBST (root->right));
}
int main () {
struct Node *root = newNode (67);
root->left = newNode (72);
root->right = newNode (77); root->left->left = newNode (57);
printf ("Size of the largest BST is %d", largestBST (root));
return 0;
} आउटपुट
Size of the largest BST is 2
निष्कर्ष
इस समस्या में, हमने सीखा कि बाइनरी ट्री और बाइनरी सर्च ट्री क्या है और रिकर्सन की मदद से दिए गए बाइनरी ट्री में सबसे बड़ा BST कैसे पता करें। रिकर्सन की मदद से, हम यह पता लगाएंगे कि प्रत्येक नोड के तहत एक सबट्री बीएसटी है या नहीं और उसके अनुसार मान लौटाएं।