আমাদের একটি বাইনারি সার্চ ট্রি (BST) ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হলো সেই BST-তে কতগুলো সাবট্রি আছে যাদের সব নোডের ভ্যালু দেওয়া রেঞ্জ (start এবং end)-এর মধ্যে পড়ে। যদি start=5 এবং end=50 হয়, তবে যেসব সাবট্রির সকল নোডের ওয়েট ৫ থেকে ৫০-এর মধ্যে থাকে, তাদের কাউন্ট করা।
ইনপুট
ট্রি (চিত্রে দেখানো) - রেঞ্জ [3-6]
আউটপুট: রেঞ্জে পড়া ট্রির কাউন্ট - 2
ব্যাখ্যা: নোড ৪ এবং ৬ এর জন্য। তাদের সাবট্রি (NULL) ৩-৬ রেঞ্জের মধ্যে পড়ে।
ইনপুট
ট্রি (চিত্রে দেখানো) - রেঞ্জ [12-20]
আউটপুট: রেঞ্জে পড়া ট্রির কাউন্ট - 3
ব্যাখ্যা: নোড ১৬, ১৪ এবং ২০ এর জন্য। তাদের সাবট্রি ১২-২০ রেঞ্জের মধ্যে পড়ে।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- Btreenode স্ট্রাকচার দিয়ে ট্রি নোড তৈরি করা (info পর্ব ইন্টিজার, লেফট এবং রাইট পয়েন্টার)।
- insert(int data) ফাংশন দিয়ে ডেটা সহ নোড তৈরি করা (লেফট/রাইট NULL)।
- insert ফাংশন কল করে BST তৈরি করা (রুটের লেফট/রাইটে নোড যোগ করা)।
- l এবং h ভেরিয়েবলে রেঞ্জের মিনিমাম এবং ম্যাক্সিমাম ভ্যালু স্টোর করা।
- count ভেরিয়েবল ০ দিয়ে ইনিশিয়ালাইজ করা।
- getBtreeCount(Btreenode* root, int low, int high, int* count) ফাংশন রিকার্সিভলি কল করে প্রতিটি নোডের লেফট ও রাইট সাবট্রি চেক করা।
- যদি রুট NULL হয় তবে ১ রিটার্ন (ট্রির অংশ নয়)।
- যদি লেফট ও রাইট সাবট্রি রেঞ্জের মধ্যে থাকে এবং করেন্ট নোডও রেঞ্জের মধ্যে থাকে, তবে কাউন্ট বাড়ানো এবং ১ রিটার্ন।
- শেষে count-এ আপডেটেড ভ্যালু থাকবে।
- ফলাফল প্রিন্ট করা।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
struct Btreenode {
int info;
Btreenode *left, *right;
};
int getBtreeCount(Btreenode* root, int low, int high, int* count){
if (root == NULL)
return 1;
int left = getBtreeCount(root->left, low, high, count);
int right = getBtreeCount(root->right, low, high, count);
if (left && right && root->info >= low && root->info <= high) {
++*count;
return 1;
}
return 0;
}
Btreenode* insert(int data){
Btreenode* temp = new Btreenode;
temp->info = data;
temp->left = temp->right = NULL;
return (temp);
}
int main(){
Btreenode* root = insert(50);
root->left = insert(30);
root->right = insert(70);
root->left->left = insert(20);
root->left->right= insert(40);
root->right->left = insert(60);
root->right->right = insert(80);
int l = 10;
int h = 50;
int count=0;
getBtreeCount(root, l, h, &count);
cout << "Count of subtrees lying in range: " << count;
return 0;
}আউটপুট
Count of subtrees lying in range: 3
