Inorder Successor trong BST II (có con trỏ cha) trong C++

Cho một nút trong cây tìm kiếm nhị phân (BST), tìm nút kế tiếp theo thứ tự in-order. Nút có con trỏ parent nhưng không có con trỏ gốc cây. Kế tiếp là nút có khóa nhỏ nhất lớn hơn nút hiện tại.

Giải thuật

1. Nếu nút có con phải: kế tiếp là nút trái nhất của cây con phải.
2. Nếu không có con phải: đi lên qua cha cho đến khi nút hiện tại là con trái của cha. Cha lúc đó là kế tiếp.

Ví dụ triển khai

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

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
    Node(int v, Node* par = nullptr) : val(v), left(nullptr), right(nullptr), parent(par) {}
};

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if (node->right) {
            node = node->right;
            while (node->left) node = node->left;
            return node;
        }
        while (node->parent && node != node->parent->left) {
            node = node->parent;
        }
        return node->parent;
    }
};

int main() {
    Solution ob;
    Node* root = new Node(5);
    root->left = new Node(3, root);
    root->right = new Node(6, root);
    root->left->left = new Node(2, root->left);
    root->left->right = new Node(4, root->left);
    root->left->left->left = new Node(1, root->left->left);
    cout << ob.inorderSuccessor(root->left->left)->val;
    return 0;
}

Đầu vào

Nút có giá trị 2 trong cây BST

Đầu ra

3