C++-এ BST-তে Inorder Successor

ধরুন আমাদের একটি বাইনারি সার্চ ট্রি এবং এতে একটি নোড আছে, আমাদের BST-এ সেই নোডের ইন-অর্ডার উত্তরাধিকারী অনুসন্ধান করতে হবে। আমরা জানি যে একটি নোড p-এর উত্তরসূরি হল p.val-এর চেয়ে ছোট কী সহ নোড।

সুতরাং, যদি ইনপুট রুট =[2,1,3], p =1,

তাহলে আউটপুট হবে 2,

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন inorderSuccessor(), এটি রুট এবং p

  নেবে

• যদি রুট নাল হয়, তাহলে −

  • রিটার্ন নাল

• যদি মূলের 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;
}

ইনপুট

{2,1,3},1

আউটপুট

2