Phần tử lớn nhất trên đường đi giữa hai nút của BST trong C++

Đề bài

Cho mảng N phần tử và hai số A, B thuộc mảng. Xây dựng BST bằng cách chèn lần lượt các phần tử. Tìm phần tử lớn nhất trên đường đi từ A đến B.

Ví dụ: Mảng {24, 23, 15, 36, 19, 41, 25, 35}. BST hình thành như hình. Với A=19, B=41, phần tử lớn nhất trên đường đi là 41.

Thuật toán

1. Tìm tổ tiên chung gần nhất (LCA) của A và B.
2. Tìm max trên đường từ LCA đến A (gọi max1).
3. Tìm max trên đường từ LCA đến B (gọi max2).
4. Trả về max(max1, max2).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

Node* createNode(int x) {
    Node* p = new Node();
    p->data = x;
    p->left = p->right = nullptr;
    return p;
}

void insertNode(Node* root, int x) {
    Node *p = root, *q = nullptr;
    while (p) {
        q = p;
        if (p->data < x) p = p->right;
        else p = p->left;
    }
    if (!q) p = createNode(x);
    else if (q->data < x) q->right = createNode(x);
    else q->left = createNode(x);
}

// Tìm max trên đường từ node q đến giá trị x
int maxelpath(Node* q, int x) {
    Node* p = q;
    int mx = INT_MIN;
    while (p->data != x) {
        mx = max(mx, p->data);
        if (p->data > x) p = p->left;
        else p = p->right;
    }
    return max(mx, x);
}

// Tìm LCA và trả về max trên đường A-B
int getMaximumElement(Node* root, int x, int y) {
    Node* p = root;
    // Tìm LCA
    while ((x < p->data && y < p->data) || (x > p->data && y > p->data)) {
        if (x < p->data && y < p->data) p = p->left;
        else 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]);
    Node* root = createNode(arr[0]);
    for (int i = 1; i < n; i++) insertNode(root, arr[i]);
    cout << "Phan tu lon nhat = " << getMaximumElement(root, a, b) << endl;
    return 0;
}

Kết quả

Phan tu lon nhat = 41