বাইনারি ট্রি হল এমন ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের দুটি চাইল্ড নোড থাকে (বাম এবং ডান)। BST (বাইনারি সার্চ ট্রি) হল এমন ট্রি যেখানে বাম সাবট্রির নোডগুলোর মান রুট থেকে ছোট এবং ডান সাবট্রির মান বড়।
এখানে আমরা চেক করব একটি বাইনারি ট্রি কি BST। এর জন্য প্রতিটি নোডে BST শর্ত চেক করতে হবে: বাম চাইল্ড < রুট < ডান চাইল্ড, এবং সাবট্রিও BST হতে হবে।
বাইনারি ট্রি BST কিনা চেক করার প্রোগ্রাম
#include<bits/stdc++.h> #include<iostream> using namespace std; class node { public: int data; node* left; node* right; node(int data) { this->data = data; this->left = NULL; this->right = NULL; } }; int isBSTUtil(node* node, int min, int max); int isBST(node* node) { return(isBSTUtil(node, INT_MIN, INT_MAX)); } int isBSTUtil(node* node, int min, int max) { if (node==NULL) return 1; if (node->data < min || node->data > max) return 0; return isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max); } int main() { node *root = new node(8); root->left = new node(3); root->right = new node(10); root->left->left = new node(1); root->left->right = new node(6); if(isBST(root)) cout<<"The given tree is a BST"; else cout<<"The given tree is Not a BST"; return 0; }আউটপুট
The given tree is a BST
কোড ব্যাখ্যা
উপরের কোডটি BST চেক করে। main() মেথড একটি ট্রি তৈরি করে isBST() কল করে। এই মেথড বাম এবং ডান চাইল্ড BST নিয়ম মেনে চলে কিনা এবং সাবট্রিগুলোও BST কিনা তা isBSTUtil() দিয়ে চেক করে।
