আমাদের একটি বাইনারি সার্চ ট্রি (BST) এবং একটি রেঞ্জ [low, high] দেওয়া আছে। কাজ হল BST-এ সেই রেঞ্জের মধ্যে পড়া নোডের সংখ্যা গণনা করা।
BST-এ বাম সাবট্রির সব নোডের মান পেরেন্ট নোডের মানের চেয়ে ছোট বা সমান, এবং ডান সাবট্রির সব নোডের মান পেরেন্টের চেয়ে বড় হয়।
উদাহরণ:
রেঞ্জ: [11, 40] → আউটপুট: count is: 5 (নোড: 14, 19, 27, 31, 35)
অ্যালগরিদম
যদি root == NULL হয় তবে ০ রিটার্ন করুন
যদি root->data == low && root->data == high হয় তবে ১ রিটার্ন করুন
যদি root->data রেঞ্জের মধ্যে পড়ে (low <= data <= high): ১ + left subtree-এ কল + right subtree-এ কল
যদি root->data < low: শুধু right subtree-এ কল করুন
যদি root->data > high: শুধু left subtree-এ কল করুন
প্রোগ্রাম
#include <iostream>
using namespace std;
struct node {
int data;
struct node* left, *right;
};
node* newNode(int data) {
node* temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int findcount(node* root, int low, int high) {
if (!root) return 0;
if (root->data == high && root->data == low) return 1;
if (root->data <= high && root->data >= low)
return 1 + findcount(root->left, low, high) + findcount(root->right, low, high);
else if (root->data < low)
return findcount(root->right, low, high);
else
return findcount(root->left, low, high);
}
int main() {
node* root = newNode(27);
root->left = newNode(14);
root->right = newNode(35);
root->left->left = newNode(10);
root->left->right = newNode(19);
root->right->left = newNode(31);
root->right->right = newNode(42);
int low = 10, high = 50;
cout << "Count of nodes between [" << low << ", " << high << "] is " << findcount(root, low, high);
return 0;
}
আউটপুট
Count of nodes between [10, 50] is 7
