C++-এ বাইনারি ট্রিতে সবচেয়ে বড় BST খুঁজে বের করা

বাইনারি ট্রিতে প্রতিটি নোডের দুটি চাইল্ড থাকে (বাম ও ডান)। বাইনারি সার্চ ট্রি (BST) একটি বিশেষ বাইনারি ট্রি যেখানে:

• বাম চাইল্ড প্যারেন্ট থেকে ছোট
• ডান চাইল্ড প্যারেন্ট থেকে বড়

একটি বাইনারি ট্রি দেওয়া থাকলে, তার ভিতরে সবচেয়ে বড় BST খুঁজে বের করতে হবে।

উদাহরণ

ইনপুট ১: রুট ১০, বাম ৫, ডান ১৫, ৫-এর বাম ১, ডান ৮, ১৫-এর বাম ৭। সাবট্রি ৫-১-৮ BST, আকার ৩।
ইনপুট ২: রুট ৫২, বাম ৩৭, ডান ৬৭, ৩৭-এর বাম ১২, ডান ২৭, ৬৭-এর বাম ৫৭, ডান ৭৭, ৭৭-এর বাম ৭২, ডান ৮৭। আউটপুট: ৫।

সমাধানের পদ্ধতি

প্রতিটি নোড x-এর জন্য: বাম সাবট্রির সব নোড x-র চেয়ে ছোট, ডান সাবট্রির সব নোড x-র চেয়ে বড়, এবং উভয় সাবট্রি BST হলে সেটি BST। ইন-অর্ডার ট্রাভার্সাল এবং রিকার্সন ব্যবহার করে প্রতিটি নোড চেক করুন।

উদাহরণ

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

struct Node { 
    int data; 
    Node* left; 
    Node* right; 
}; 

Node* newNode(int data) { 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 

struct Detail { 
    int size, max, min, ans; 
    bool isBST; 
}; 

bool isBST(Node* root, int min, int max) { 
    if (!root) 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) return 0; 
    return 1 + size(root->left) + size(root->right); 
} 

int largestBST(Node* root) { 
    if (isBST(root, INT_MIN, INT_MAX)) return size(root); 
    return max(largestBST(root->left), largestBST(root->right)); 
} 

int main() { 
    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-এর আকার বের করা হয়েছে।