এই সমস্যায়, আমাদের একটি বাইনারি অনুসন্ধান গাছের দুটি নোড দেওয়া হয়েছে। এবং আমাদের k1 থেকে k2 রেঞ্জের সমস্ত মান প্রিন্ট করতে হবে যা গাছে ঘটে। অর্থাৎ k1-এর থেকে বড় এবং k2-এর থেকে ছোট সব মানই আমাদের প্রিন্ট করতে হবে। এবং আমাদের এই সমস্ত কীগুলিকে তাদের মান বৃদ্ধির ক্রমে প্রিন্ট করতে হবে।
বাইনারী সার্চ ট্রি একটি গাছ যা এই 3টি বৈশিষ্ট্য অনুসরণ করে -
-
বাম সাবট্রিতে নোড আছে যার মান নোডের মানের থেকে কম।
-
ডান সাবট্রিতে একটি নোড আছে যার মান নোডের মানের চেয়ে বেশি।
-
একটি সাবট্রি’স নেওয়াও একটি বাইনারি সার্চ ট্রি হওয়া উচিত। গাছে কোনো ডুপ্লিকেট নোড অনুমোদিত নয়৷
উদাহরণ ,
বিষয়টি আরও ভালভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : k1 = 12 and k2 = 25. Output : 15, 20, 24
গাছ৷ -
ব্যাখ্যা − গাছটি অতিক্রম করার সময়, সমস্ত উপাদানগুলিকে অতিক্রম করা হবে এবং 12 থেকে 25 রেঞ্জের মধ্যে থাকা উপাদানগুলি যেমন একটি নোড x, 12 ≤ x ≥ 25 এর জন্য প্রিন্ট করা হবে৷
এখানে, আমরা আমাদের সমাধান খুঁজে পেতে BST এর বৈশিষ্ট্যগুলি ব্যবহার করব। অর্থাৎ বাম সাবট্রির সমস্ত উপাদান রুট থেকে ছোট এবং ডান সাবট্রির সমস্ত উপাদান রুট নোডের চেয়ে বড়। এবং আমরা এই সমস্যা সমাধানের জন্য BST এর ক্রমানুসারে ব্যবহার করব। এখন, এই সমস্যাটি সমাধান করার জন্য একটি অ্যালগরিদম তৈরি করা যাক।
অ্যালগোরিদম
Step 1 : Compare the root node with the k1 and k2. Step 2 : If root is greater than k1. Call left subtree for the search recursively. Step 3 : If root is smaller than k2. Call right subtree for the search recursively. Step 4 : If the root of the tree is in the range. Then print the root’s value.
উদাহরণ
এখন, এই অ্যালগরিদমের উপর ভিত্তি করে, আসুন সমস্যা সমাধানের জন্য একটি প্রোগ্রাম তৈরি করি৷
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
};
void nodesInRange(node *root, int k1, int k2){
if ( NULL == root )
return;
if ( k1 < root->data )
nodesInRange(root->left, k1, k2);
if ( k1 <= root->data && k2 >= root->data )
cout<<root->data<<"\t";
if ( k2 > root->data )
nodesInRange(root->right, k1, k2);
}
node* insert(int data){
node *temp = new node();
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int main(){
node *root = new node();
int k1 = 12, k2 = 25;
root = insert(20);
root->left = insert(10);
root->right = insert(24);
root->left->left = insert(8);
root->left->right = insert(15);
root->right->right = insert(32);
cout<<”The values of node within the range are\t”;
nodesInRange(root, k1, k2);
return 0;
} আউটপুট
The values of node within the range are 15 20 24.
