C++ में BST में इनऑर्डर सक्सेसर खोजें - सबसे छोटा बड़ा कुंजी

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री BST और एक नोड का मान है, हमें BST में उस नोड का इनऑर्डर सक्सेसर ढूंढना है। जैसा कि हम सभी जानते हैं कि नोड p का सक्सेसर वह नोड है जिसकी कुंजी p के मान से सबसे छोटी बड़ी है।

उदाहरण के लिए, यदि इनपुट इस तरह का ट्री है:

और p = 1, तो आउटपुट 2 होगा।

समाधान दृष्टिकोण

BST गुण का उपयोग करके पुनरावर्ती दृष्टिकोण:

1. पुनरावर्ती विधि inorderSuccessor() परिभाषित करें जो root और p लेती है
2. यदि root null है, तो null लौटाएं
3. यदि root का मान <= p का मान, तो दाएं उपट्री में खोजें
4. अन्यथा:
   • option := बाएं उपट्री में inorderSuccessor()
   • लौटाएं (यदि option शून्य है तो root, अन्यथा option)

C++ कार्यान्वयन

#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; 
        } 
    } 
}; 

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;
}

इनपुट

TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); 1

आउटपुट

2