ধরুন আমাদের একটি বাইনারি সার্চ ট্রি BST এবং একটি নোডের আরেকটি মান আছে, আমাদের BST-এ সেই নোডের ইন-অর্ডার উত্তরাধিকারী খুঁজে বের করতে হবে। আমরা সবাই জানি যে একটি নোড p-এর উত্তরসূরী হল সেই নোড যার মানের চেয়ে ছোট কী আছে।
সুতরাং, যদি ইনপুট মত হয়
এবং p =1, তাহলে আউটপুট হবে 2,
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন inorderSuccessor(), এটি রুট করবে এবং p
- যদি রুট নাল হয়, তাহলে:
- শূন্য রিটার্ন
- যদি root-এর val <=p-এর val হয়, তাহলে:
- inorderSuccessor (রুটের ডানদিকে , p) ফেরত দিন
- অন্যথায়
- বিকল্প :=inorderSuccessor(রুটের বামে , p)
- রিটার্ন (যদি বিকল্প শূন্য হয়, তাহলে রুট, অন্যথায় বিকল্প)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
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;
}
}
};
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;
} ইনপুট
TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); 1
আউটপুট
2
