সমস্যা বিবরণ
একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হল ট্রিয়ে সর্বোচ্চ আকারের BST (Binary Search Tree) সাবট্রি বের করা।
উদাহরণ
ইনপুট ট্রি (চিত্র) — পুরো ট্রিই BST, আউটপুট: ৩ (নোড সংখ্যা)।
পদ্ধতি ১: ইন-অর্ডার ট্রাভার্সাল + BST চেক (O(n²))
প্রতিটি নোডের জন্য এর সাবট্রি কি BST তা চেক করে সর্বোচ্চ আকার বের করা।
পদ্ধতি ২: বটম-আপ ট্রাভার্সাল (O(n)) - অপ্টিমাইজড
নিচ থেকে উপরে ট্রাভার্সাল করে প্রতিটি নোডের জন্য মিন/ম্যাক্স ভ্যালু, BST স্ট্যাটাস, আকার ট্র্যাক করা।
#include <bits/stdc++.h>
using namespace std;
struct Node { int data; Node *left, *right; };
int largestBST(Node* root) {
int maxSize=0;
function<tuple<bool,int,int,int>(Node*)> dfs = [&](Node* n) -> tuple<bool,int,int,int> {
if(!n) return {true, INT_MAX, INT_MIN, 0};
auto [lBST, lMin, lMax, lSize] = dfs(n->left);
auto [rBST, rMin, rMax, rSize] = dfs(n->right);
bool isBST = lBST && rBST && (n->data > lMax) && (n->data < rMin);
int sz = isBST ? lSize + rSize + 1 : 0;
maxSize = max(maxSize, sz);
int mn = min(n->data, min(lMin, rMin));
int mx = max(n->data, max(lMax, rMax));
return {isBST, mn, mx, sz};
};
dfs(root);
return maxSize;
}
আউটপুট
The Size of the largest BST is 5
