Inorder Successor ใน BST II (มี parent pointer) ใน C++

เราได้รับโหนดใน Binary Search Tree (BST) ที่มี pointer 指向 parent เป้าหมายคือหา inorder successor ของโหนดนั้น (โหนดที่มีค่าน้อยที่สุดที่มากกว่าโหนดปัจจุบัน)

ตัวอย่าง

BST:

      5
     / \
    3   6
   / \
  2   4
 /
1

โหนด 2 → Inorder successor คือ 3

แนวทางการแก้ปัญหา

1. กรณีที่ 1: โหนดมี right child → Successor คือโหนดซ้ายสุดใน right subtree
2. กรณีที่ 2: โหนดไม่มี right child → ขึ้นไปหา parent จนกว่าโหนดปัจจุบันจะเป็น left child ของ parent → Successor คือ parent นั้น

การนำไปใช้ (Implementation)

#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) {
        // กรณีที่ 1: มี right child
        if (node->right) {
            node = node->right;
            while (node->left) node = node->left;
            return node;
        }
        
        // กรณีที่ 2: ไม่มี right child - ขึ้นหา parent
        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; // 3
    return 0;
}

อินพุต

Node 2 in the BST above

เอาต์พุต

3