एक बाइनरी ट्री में, प्रत्येक चाइल्ड नोड में केवल दो नोड (बाएं और दाएं) होते हैं। ट्री संरचनाएं डेटा का सरल प्रतिनिधित्व हैं। बाइनरी सर्च ट्री (BST) विशेष प्रकार के बाइनरी ट्री हैं जो इन शर्तों को पूरा करते हैं:
अपने पैरेंट की तुलना में, बायां चाइल्ड नोड छोटा होता है
दाएं चाइल्ड का पैरेंट नोड चाइल्ड नोड से बड़ा होता है
मान लीजिए हमें एक बाइनरी ट्री दिया गया है, और हमें यह पता लगाना है कि उसके भीतर सबसे बड़ा बाइनरी सर्च ट्री (BST) क्या है।
इस कार्य में, हम एक बाइनरी ट्री में सबसे बड़ा BST ढूंढने के लिए एक फ़ंक्शन बनाएंगे। जब बाइनरी ट्री स्वयं एक BST होता है, तो पूरे बाइनरी ट्री का आकार निर्धारित करना संभव होता है। एक उदाहरण के रूप में -
इनपुट
10 / \ 5 15 /\ \ 1 8 7
जैसा कि दिखाया गया है, इस मामले में हाइलाइट किया गया BST सबट्री सबसे बड़ा है। '3' सबट्री का आकार है, इसलिए रिटर्न मान सबट्री का आकार है।
इनपुट
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
आउटपुट
5
सबट्री जिनके नोड्स की लंबाई उनके पैरेंट नोड्स की लंबाई से कम है, उनमें अधिकतम तीन आकार के BST नोड्स होते हैं।
दिए गए बाइनरी ट्री में सबसे बड़ा BST ढूंढने का दृष्टिकोण
हर नोड x के लिए, एक बाइनरी ट्री BST है यदि निम्नलिखित बिंदु मान्य हैं। एक नोड के बाएं सबट्री में केवल वही नोड्स दिखाई देते हैं जिनका डेटा उनके पैरेंट नोड से कम होता है। केवल एक नोड हो सकता है जिसके पास अपने पैरेंट नोड से अधिक डेटा हो। बाएं और दाएं दोनों सबट्री को बाइनरी सर्च ट्री (BST) द्वारा चरित्रित किया जाना चाहिए।
एल्गोरिदम होगा -
हम बाइनरी ट्री की रूट से शुरू करेंगे और पुनरावृत्ति का उपयोग करके इन-ऑर्डर ट्रैवर्सल करेंगे। वर्तमान नोड 'ROOT' के लिए, हम निम्नलिखित करेंगे-
यदि यह एक वैध 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 कैसे ढूंढें। पुनरावृत्ति की मदद से, हम पता लगाएंगे कि हर नोड के तहत एक सबट्री BST है या नहीं और तदनुसार मान वापस करेंगे।
