C++-এ BST-এ ইনঅর্ডার সাকসেসর (Inorder Successor) বের করা II

ধরি আমাদের একটি বাইনারি সার্চ ট্রি (BST)-এর একটি নোড দেওয়া আছে। আমাদের সেই নোডের ইনঅর্ডার সাকসেসর (in-order successor) বের করতে হবে। যদি কোনো ইনঅর্ডার সাকসেসর নেই, তবে null রিটার্ন করুন। ইনঅর্ডার সাকসেসর হলো সেই নোড যেটির কী (key) বর্তমান নোডের কী-র চেয়ে ছোট হলেও সবচেয়ে বড়।

আমাদের নোডে ডাইরেক্ট অ্যাক্সেস আছে কিন্তু রুটে (root) নেই। প্রতিটি নোডের প্যারেন্ট নোডের রেফারেন্স রয়েছে। নোডের ডেফিনিশন:

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

ইনপুট উদাহরণ:

নোড = ২ হলে আউটপুট = ৩।

সমাধানের ধাপসমূহ:

যদি নোডের ডান সন্তান (right) null নয়:
- node := node->right
- while (node->left != null): node := node->left
- return node
while (node->parent != null && node != node->parent->left):
- node := node->parent
return node->parent

উদাহরণ

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

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
    Node(int v, Node* par = NULL) {
        val = v;
        left = NULL;
        right = NULL;
        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;
}

ইনপুট

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); (ob.inorderSuccessor(root->left->left))->val