আমাদের একটি বাইনারি ট্রি ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হলো এর মধ্যে কতগুলো বাইনারি সার্চ ট্রি (BST) সাবট্রি হিসেবে আছে তা বের করা। একটি BST হলো এমন বাইনারি ট্রি যেখানে লেফট চাইল্ড রুট থেকে ছোট এবং রাইট চাইল্ড রুট থেকে বড়।
ইনপুট
ভ্যালুগুলো ইনপুট দিয়ে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:
আউটপুট
Count the Number of Binary Search Trees present in a Binary Tree are: 2
ব্যাখ্যা
আমাদের একটি ইন্টিজার অ্যারে দেওয়া আছে जिससे বাইনারি ট্রি তৈরি করা হয়েছে। আমরা চেক করব কোনো বাইনারি সার্চ ট্রি আছে কিনা। প্রতিটি রুট নোড একটি বাইনারি সার্চ ট্রি রিপ্রেজেন্ট করে, তাই দिये गये বাইনারি ট্রিতে দেখা যায় কোনো অন্য বাইনারি সার্চ ট্রি নেই, তাই কাউন্ট হলো ২ যা এই ট্রির মোট লিফ নোডের সংখ্যা।
ইনপুট
ভ্যালুগুলো ইনপুট দিয়ে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:
আউটপুট
Count the Number of Binary Search Trees present in a Binary Tree are: 6
ব্যাখ্যা
দیا गये বাইনারি ট্রিতে ৪টি লিফ নোড এবং দুটি সাবট্রি আছে যা BST তৈরি করছে, তাই মোট কাউন্ট ৬।
প্রোগ্রামে ব্যবহৃত পদ্ধতি:
এই পদ্ধতিতে আমরা নোড N-এর লেফট সাবট্রির সর্বোচ্চ মান বের করি এবং চেক করি এটা N-এর চেয়ে ছোট কিনা। আবার রাইট সাবট্রির সর্বনিম্ন মান বের করি এবং চেক করি এটা N-এর চেয়ে বড় কিনা। দুটো শর্ত পূরণ করলে সেটি BST। বটম-আপ манনারে ট্রভারস করে শর্তগুলো চেক করে BST-এর কাউন্ট বাড়ানো হয়।
- প্রতিটি নোডের নোড_ডেটায় থাকে: BST-এর সংখ্যা, সাবট্রির সর্বোচ্চ মান, সর্বনিম্ন মান, বুলিয়ান ভ্যালু (সাবট্রি BST কিনা)।
BST_present(struct tree_node* parent)ফাংশন পেরেন্ট নোডে রুট করা বাইনারি ট্রি ভেতরে কতগুলো BST আছে তা বের করে।- পেরেন্ট NULL হলে রিটার্ন
{0, min, max, true}যেখানে min=INT_MIN, max=INT_MAX। - লেফট ও রাইট চাইল্ড উভয় NULL হলে রিটার্ন
{1, parent->data, parent->data, true}। node_data Left = BST_present(parent->left)এবংnode_data Right = BST_present(parent->right)সেট করা হয়।n1.lowest = min(parent->data, min(Left.lowest, Right.lowest))এবংn1.highest = max(parent->data, max(Left.highest, Right.highest))।- যদি
(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest)সত্য হয় তবেn1.check = trueএবংn1.total_bst = 1 + Left.total_bst + Right.total_bst। - অন্যথায়
n1.check = falseএবংn1.total_bst = Left.total_bst + Right.total_bst। - শেষে n1 রিটার্ন করা হয়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct tree_node {
struct tree_node* left;
struct tree_node* right;
int data;
tree_node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
struct node_data {
int total_bst;
int highest, lowest;
bool check;
};
node_data BST_present(struct tree_node* parent) {
if (parent == NULL) {
int max = INT_MAX;
int min = INT_MIN;
return { 0, min, max, true };
}
if (parent->left == NULL) {
if (parent->right == NULL) {
return { 1, parent->data, parent->data, true };
}
}
node_data Left = BST_present(parent->left);
node_data Right = BST_present(parent->right);
node_data n1;
n1.lowest = min(parent->data, min(Left.lowest, Right.lowest));
n1.highest = max(parent->data, max(Left.highest, Right.highest));
if (Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest) {
n1.check = true;
n1.total_bst = 1 + Left.total_bst + Right.total_bst;
} else {
n1.check = false;
n1.total_bst = Left.total_bst + Right.total_bst;
}
return n1;
}
int main() {
struct tree_node* root = new tree_node(3);
root->left = new tree_node(7);
root->right = new tree_node(4);
root->left->left = new tree_node(5);
root->right->right = new tree_node(1);
root->left->left->left = new tree_node(10);
cout << "Count the Number of Binary Search Trees present in a Binary Tree are: " << BST_present(root).total_bst;
return 0;
}
আউটপুট
Count the Number of Binary Search Trees present in a Binary Tree are: 2
