C++ में BST में इनऑर्डर सक्सेसर - पुनरावर्ती समाधान

समस्या विवरण

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

उदाहरण के लिए, यदि इनपुट root = [2,1,3], 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;
}

इनपुट

{2,1,3},1

आउटपुट

2