বাইনারি ট্রিতে সর্বোচ্চ সাব-ট্রি যোগফল যেটি BST ও (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের একটি বাইনারি ট্রি BT দেওয়া আছে। আমাদের কাজ হল বাইনারি ট্রিতে সর্বোচ্চ সাব-ট্রি যোগফল খুঁজে বের করার প্রোগ্রাম তৈরি করা যাতে সাব-ট্রিটিও একটি BST হয়।

বাইনারি ট্রির একটি বিশেষ শর্ত আছে যে প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে।

বাইনারি সার্চ ট্রি (BST) হল এমন একটি ট্রি যেখানে সকল নোড নিচের বৈশিষ্ট্যগুলো মেনে চলে:

• বাম সাব-ট্রির কি (key) এর মান তার পিতামাতা (রুট) নোডের কি-এর মান থেকে ছোট।
• ডান সাব-ট্রির কি (key) এর মান তার পিতামাতা (রুট) নোডের কি-এর মান থেকে বড় বা সমান।

32

এখানে, আমাদের দুটি সাবট্রি আছে যা BST। তাদের যোগফল:

7 + 3 + 22 = 32
6 + 5 + 17 = 28
সর্বোচ্চ = 32।

একটি সহজ সমাধান হল ট্রি ডেটা স্ট্রাকচার ট্রভার্স করে প্রতিটি নোডে চেক করা যে এর চাইল্ড নোডগুলো বাইনারি সার্চ ট্রি তৈরি করতে পারে কিনা। আমরা BST গঠনকারী সকল নোডের যোগফল বের করব এবং সব BST যোগফলের মধ্যে সর্বোচ্চটি ফেরত দিব।

#include 
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