सी++ में बीएसटी में इनऑर्डर उत्तराधिकारी

मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है और उसमें एक नोड है, तो हमें उस नोड के इन-ऑर्डर सक्सेसर को BST में खोजना होगा। जैसा कि हम जानते हैं कि एक नोड p का उत्तराधिकारी वह नोड होता है जिसकी सबसे छोटी कुंजी p.val से बड़ी होती है।

इसलिए, यदि इनपुट रूट =[2,1,3], p =1,

तो आउटपुट 2 होगा,

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• पुनरावर्ती विधि inorderSuccessor() को परिभाषित करें, यह जड़ लेगा और p

• यदि रूट अशक्त है, तो -

  • वापसी शून्य

• यदि मूल का मान <=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