मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री BST है और एक नोड का दूसरा मान है, तो हमें BST में उस नोड के इन-ऑर्डर सक्सेसर को खोजना होगा। जैसा कि हम सभी जानते हैं कि एक नोड p का उत्तराधिकारी वह नोड होता है जिसकी सबसे छोटी कुंजी p के मान से अधिक होती है।
तो, अगर इनपुट पसंद है
और 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;
} इनपुट
TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); 1
आउटपुट
2