C++のBSTの2つのノード間の最大要素

問題の説明

N個の要素の配列と、指定された配列に属する2つの整数A、Bが与えられます。 arr[0]からarr[n-1]に要素を挿入して、二分探索木を作成します。タスクは、AからBへのパスで最大の要素を見つけることです。

例

配列が{24、23、15、36、19、41、25、35}の場合、次のようにBSTを形成できます-

A=19およびB=41とすると、これら2つのノード間の最大要素は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