সমস্যা বিবরণ
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 বলুন।
- max1 এবং 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
