समस्या कथन
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
