সমস্যা বিবৃতি
N উপাদানগুলির একটি অ্যারে এবং দুটি পূর্ণসংখ্যা A, B দেওয়া হয়েছে যা প্রদত্ত অ্যারের অন্তর্গত। arr[0] থেকে arr[n-1] এ উপাদান সন্নিবেশ করে একটি বাইনারি সার্চ ট্রি তৈরি করুন। কাজ হল A থেকে B পর্যন্ত পাথে সর্বাধিক উপাদান খুঁজে বের করা।
উদাহরণ
যদি অ্যারেটি হয় {24, 23, 15, 36, 19, 41, 25, 35} তাহলে আমরা নিম্নরূপ BST গঠন করতে পারি -
যদি আমরা A =19 এবং B =41 বিবেচনা করি তবে এই দুটি নোডের মধ্যে সর্বাধিক উপাদান হল 41
অ্যালগরিদম
- নোড A এবং B এর সর্বনিম্ন সাধারণ পূর্বপুরুষ (LCA) খুঁজুন।
- LCA এবং A-এর মধ্যে সর্বাধিক নোড খুঁজুন। আসুন এটিকে max1 হিসাবে বলি
- LCA এবং B-এর মধ্যে সর্বাধিক নোড খুঁজুন। আসুন এটিকে max2 বলি
- সর্বোচ্চ 1 এবং max2 ফেরত দিন
উদাহরণ
আসুন এখন একটি উদাহরণ দেখি -
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node* left;
struct node* right;
};
node *createNode(int x) {
node *p = new node();
p -> data = x;
p -> left = NULL;
p -> right = NULL;
return p;
}
void insertNode(struct node *root, int x) {
node *p = root, *q = NULL;
while (p != NULL) {
q = p;
if (p -> data < x) {
p = p -> right;
} else {
p = p -> left;
}
}
if (q == NULL) {
p = createNode(x);
} else {
if (q -> data < x) {
q -> right = createNode(x); } else {
q -> left = createNode(x);
}
}
}
int maxelpath(node *q, int x) {
node *p = q;
int mx = INT_MIN;
while (p -> data != x) {
if (p -> data > x) {
mx = max(mx, p -> data);
p = p -> left;
} else {
mx = max(mx, p -> data);
p = p -> right;
}
}
return max(mx, x);
}
int getMaximumElement(struct node *root, int x, int y) {
node *p = root;
while ((x < p -> data && y < p -> data) || (x > p ->
data && y > p -> data)) {
if (x < p -> data && y < p -> data) {
p = p -> left;
} else if (x > p -> data && y > p -> data) {
p = p -> right;
}
}
return max(maxelpath(p, x), maxelpath(p, y));
}
int main() {
int arr[] = {24, 23, 15, 36, 19, 41, 25, 35}; int a = 19, b = 41;
int n = sizeof(arr) / sizeof(arr[0]);
struct node *root = createNode(arr[0]);
for (int i = 1; i < n; i++) insertNode(root, arr[i]);
cout << "Maximum element = " << getMaximumElement(root, a, b) << endl;
return 0;
} আউটপুট
Maximum element = 41
