C++ এ বাইনারি ট্রিতে সবচেয়ে বড় BST

একটি বাইনারি গাছে, প্রতিটি চাইল্ড নোডে মাত্র দুটি নোড (বাম এবং ডান) থাকে। গাছের গঠনগুলি কেবল ডেটার উপস্থাপনা। বাইনারি সার্চ ট্রি (বিএসটি) হল বিশেষ ধরনের বাইনারি ট্রি যা এই শর্তগুলি পূরণ করে −

এর পিতামাতার তুলনায়, বাম শিশু নোডটি ছোট
ডান সন্তানের প্যারেন্ট নোড চাইল্ড নোডের চেয়ে বড়

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

এই টাস্কে, আমরা একটি বাইনারি ট্রিতে সবচেয়ে বড় BST খুঁজে বের করার জন্য একটি ফাংশন তৈরি করব। যখন বাইনারি গাছ নিজেই একটি BST হয়, তখন সম্পূর্ণ বাইনারি গাছের আকার নির্ধারণ করা সম্ভব। উদাহরণ হিসেবে −

ইনপুট

দেখানো হিসাবে, BST সাবট্রি হাইলাইট, এই ক্ষেত্রে, বৃহত্তম. '3' হল সাবট্রির সাইজ, তাই রিটার্ন ভ্যালু হল সাবট্রির সাইজ।

ইনপুট

52
/ \
37 67
/\ / \
12 27 57 77
/\
72 87

আউটপুট

নোড সহ সাবট্রি যাদের দৈর্ঘ্য তাদের প্যারেন্ট নোডের দৈর্ঘ্যের চেয়ে কম তাদের তিনটি আকার পর্যন্ত BST নোড থাকে৷

প্রদত্ত বাইনারি ট্রিতে সবচেয়ে বড় BST খুঁজে বের করার পদ্ধতি

প্রতিটি নোড x এর জন্য, একটি বাইনারি ট্রি হল BST যদি নিম্নলিখিত পয়েন্টগুলি বৈধ হয়। শুধুমাত্র যে নোডের ডেটা তাদের প্যারেন্ট নোডের চেয়ে কম সেগুলিই নোডের বাম সাবট্রিতে উপস্থিত হয়। শুধুমাত্র একটি নোড থাকতে পারে যার মূল নোডের চেয়ে বেশি ডেটা রয়েছে। বাম এবং ডান উভয় সাবট্রিকে বাইনারি সার্চ ট্রি (BST) দ্বারা চিহ্নিত করা উচিত।

অ্যালগরিদম হবে −

আমরা বাইনারি গাছের মূল থেকে শুরু করব এবং রিকারশন ব্যবহার করে ইন-অর্ডার ট্রাভার্সাল করব। বর্তমান নোড 'ROOT'-এর জন্য, আমরা নিম্নলিখিতগুলি করব-

যদি এটি একটি বৈধ BST-এর মূল হয়, আমরা এর আকার ফেরত দিই৷
অন্যথায়, আমরা বাম এবং ডান সাবট্রিতে সবচেয়ে বড় BST পাব।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left;
   struct Node *right;
};
struct Node *
newNode (int data) {
   struct Node *node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
struct Detail {
   int size;
   int max;
   int min;
   int ans;
   bool isBST;
};
bool isBST (Node * root, int min, int max) {
   if (root == NULL) {
      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 == NULL) {
      return 0;
   }
   return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
   // Current Subtree is BST.
   if (isBST (root, INT_MIN, INT_MAX) == true) {
      return size (root);
   }
   // Find largest BST in left and right subtrees.
   return max (largestBST (root->left), largestBST (root->right));
}
int main () {
   struct 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 খুঁজে বের করতে হয়। পুনরাবৃত্তির সাহায্যে, আমরা প্রতিটি নোডের নীচে একটি সাবট্রি বিএসটি কিনা তা খুঁজে বের করব এবং সেই অনুযায়ী মান ফেরত দেব।