C++-এ Inorder Successor in BST: বাইনারি সার্চ ট্রিতে ইনঅর্ডার সাকসেসর খুঁজে বের করা

একটি বাইনারি সার্চ ট্রি (BST) এবং তার মধ্যে একটি নোড p দেওয়া আছে। p নোডের ইনঅর্ডার সাকসেসর (Inorder Successor) খুঁজে বের করতে হবে। সাকসেসর হলো p থেকেও বড় সবচেয়ে ছোট কী (key) সম্পন্ন নোড।

উদাহরণ

ইনপুট: root = [2,1,3], p = 1

আউটপুট: 2

সমাধানের পদ্ধতি (Recursive BST Property)

BST-এ ইনঅর্ডার সাকসেসর খুঁজতে রিকারসিভ অ্যালগরিদম:

1. রিকারসিভ মেথড inorderSuccessor(root, p) ডিফাইন করুন।
2. যদি root == NULL, তবে NULL রিটার্ন করুন।
3. যদি root->val <= p->val, তবে সাকসেসর ডান সাবট্রিতে থাকবে → inorderSuccessor(root->right, p) রিটার্ন করুন।
4. অন্যথায় (root->val > p->val):
   • বাম সাবট্রিতে সাকসেসর খুঁজুন: option = inorderSuccessor(root->left, p)।
   • যদি option পাওয়া যায়, তবে সেটি রিটার্ন করুন, অন্যথায় বর্তমান root ই সাকসেসর।

C++ কোড উদাহরণ

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = right = NULL;
    }
};

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(!root) return NULL;
        if(root->val <= p->val) {
            return inorderSuccessor(root->right, p);
        } else {
            TreeNode* option = inorderSuccessor(root->left, p);
            return !option ? root : option;
        }
    }
};

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

ইনপুট

{2,1,3},1

আউটপুট

2