C++-এ Largest BST Subtree: বাইনারি ট্রিতে সর্বোচ্চ BST সাবট্রি খুঁজে বের করা

একটি বাইনারি ট্রি দেওয়া আছে। এর মধ্যে সবচেয়ে বড় (সর্বোচ্চ নোড সংখ্যা সম্পন্ন) BST (Binary Search Tree) সাবট্রি খুঁজে বের করতে হবে।

উদাহরণ

আউটপুট: 3 (হাইলাইট করা BST সাবট্রিটিতে ৩টি নোড রয়েছে)।

সমাধানের পদ্ধতি (Post-order Traversal + Validation)

একটি স্ট্রাকচার Data ডিফাইন করুন যা ধারণ করবে: size (সাবট্রির সাইজ), maxVal (সাবট্রিতে সর্বোচ্চ ভ্যালু), minVal (সর্বনিম্ন ভ্যালু), ok (BST কিনা)۔
রিকারসিভ ফাংশন solve(node):
- যদি নোড নাল হয়, তবে Data(0, INT_MAX, INT_MIN, true) রিটার্ন করুন (খালি ট্রি BST)۔
- বাম ও ডান সাবট্রির জন্য রিকারসিভ কল করুন।
- বর্তমান নোডের জন্য curr ডেটা তৈরি করুন, ডিফল্ট ok = false।
- BST শর্ত চেক করুন:
  - node->val >= right.minVal হলে BST নয় → curr রিটার্ন করুন।
  - node->val <= left.maxVal হলে BST নয় → curr রিটার্ন করুন।
- যদি বাম ও ডান দুটোই BST হয় (left.ok && right.ok):
  - curr.sz = 1 + left.sz + right.sz
  - curr.ok = true
  - curr.maxVal = max(node->val, right.maxVal)
  - curr.minVal = min(node->val, left.minVal)
- যদি curr.ok হয়, তবে গ্লোবাল ret = max(ret, curr.sz) আপডেট করুন।
- curr রিটার্ন করুন।
মেইন ফাংশনে ret = 0, solve(root) কল করুন, ret রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = right = NULL;
    }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front(); q.pop();
        if(!temp->left) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            return;
        } else q.push(temp->right);
    }
}

TreeNode* make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++)
        insert(&root, v[i]);
    return root;
}

struct Data {
    int sz;
    int maxVal;
    int minVal;
    bool ok;
    Data() {}
    Data(int a, int b, int c, bool d) {
        sz = a; minVal = b; maxVal = c; ok = d;
    }
};

class Solution {
public:
    int ret;
    Data solve(TreeNode* node) {
        if (!node) return Data(0, INT_MAX, INT_MIN, true);
        Data left = solve(node->left);
        Data right = solve(node->right);
        Data curr;
        curr.ok = false;
        if (node->val >= right.minVal) return curr;
        if (node->val <= left.maxVal) return curr;
        if (left.ok && right.ok) {
            curr.sz = 1 + left.sz + right.sz;
            curr.ok = true;
            curr.maxVal = max(node->val, right.maxVal);
            curr.minVal = min(node->val, left.minVal);
        }
        if (curr.ok) ret = max(ret, curr.sz);
        return curr;
    }
    
    int largestBSTSubtree(TreeNode* root) {
        ret = 0;
        solve(root);
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {10,5,15,1,8,NULL,7};
    TreeNode *root = make_tree(v);
    cout << (ob.largestBSTSubtree(root));
    return 0;
}

ইনপুট

[10,5,15,1,8,null,7]