इस समस्या में हमें एक बाइनरी ट्री BT दिया जाता है। हमारा काम बाइनरी ट्री में अधिकतम उप-वृक्ष योग को खोजने के लिए एक प्रोग्राम बनाना है जैसे कि उप-पेड़ भी एक बीएसटी है।
बाइनरी ट्री की एक विशेष शर्त है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं।
बाइनरी सर्च ट्री एक ऐसा पेड़ है जिसमें सभी नोड्स नीचे दिए गए गुणों का पालन करते हैं
-
बाएँ उप-वृक्ष की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से कम है।
-
दाएँ उपट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से अधिक या उसके बराबर होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
आउटपुट
32
स्पष्टीकरण
यहाँ, हमारे पास दो सबट्री हैं जो BST हैं। उनका योग है,
7 + 3 + 22 = 32 6 + 5 + 17 = 28 Maximum = 32.
समाधान दृष्टिकोण
समस्या का एक सरल समाधान ट्री डेटा संरचना को पार करना और फिर प्रत्येक नोड पर जाँच करना है कि क्या यह चाइल्ड नोड बाइनरी सर्च ट्री बना सकता है या नहीं। यदि हम बीएसटी में योगदान करने वाले सभी नोड्स का योग पाते हैं और फिर पाए गए सभी बीएसटीसम का अधिकतम वापस करते हैं।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMin(int a, int b){
if(a > b)
return b;
return a;
}
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data){
this−>data = data;
this−>left = NULL;
this−>right = NULL;
}
};
struct treeVal{
int maxVal;
int minVal;
bool isBST;
int sum;
int currMax;
};
treeVal CalcBSTSumTill(struct Node* root, int& maxsum){
if (root == NULL)
return { −10000, 10000, true, 0, 0 };
if (root−>left == NULL && root−>right == NULL) {
maxsum = findMax(maxsum, root−>data);
return { root−>data, root−>data, true, root−>data, maxsum };
}
treeVal LeftSTree = CalcBSTSumTill(root−>left, maxsum);
treeVal RightSTree = CalcBSTSumTill(root−>right, maxsum);
treeVal currTRee;
if (LeftSTree.isBST && RightSTree.isBST && LeftSTree.maxVal <
root−>data && RightSTree.minVal > root−>data) {
currTRee.maxVal = findMax(root−>data,
findMax(LeftSTree.maxVal, RightSTree.maxVal));
currTRee.minVal = findMin(root−>data,
findMin(LeftSTree.minVal, RightSTree.minVal));
maxsum = findMax(maxsum, RightSTree.sum + root−>data +
LeftSTree.sum);
currTRee.sum = RightSTree.sum + root−>data +
LeftSTree.sum;
currTRee.currMax = maxsum;
currTRee.isBST = true;
return currTRee;
}
currTRee.isBST = false;
currTRee.currMax = maxsum;
currTRee.sum = RightSTree.sum + root−>data + LeftSTree.sum;
return currTRee;
}
int CalcMaxSumBST(struct Node* root){
int maxsum = −10000;
return CalcBSTSumTill(root, maxsum).currMax;
}
int main(){
struct Node* root = new Node(10);
root−>left = new Node(12);
root−>left−>right = new Node(7);
root−>left−>right−>left = new Node(3);
root−>left−>right−>right = new Node(22);
root−>right = new Node(6);
root−>right−>left = new Node(5);
root−>right−>left−>right = new Node(17);
cout<<"The maximum sub−tree sum in a Binary Tree such that the
sub−tree is also a BST is "<<CalcMaxSumBST(root);
return 0;
} आउटपुट
The maximum sub−tree sum in a Binary Tree such that the sub−tree is also a BST is 32