C++ में BST में Inorder Successor (द्वितीय संस्करण)

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री में एक नोड है, हमें उस नोड का इन-ऑर्डर सक्सेसर BST में ढूंढना है। यदि कोई इन-ऑर्डर सक्सेसर नहीं है, तो null लौटाएँ। जैसा कि हम जानते हैं कि एक नोड का सक्सेसर वह नोड है जिसका कुंजी मान नोड के मान से सबसे छोटा बड़ा होता है।

हमें नोड तक सीधी पहुंच होगी लेकिन ट्री के रूट तक नहीं। यहां प्रत्येक नोड का अपने पैरेंट नोड का संदर्भ होगा। नीचे Node की परिभाषा है:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

यदि इनपुट इस तरह है:

और नोड 2 है, तो आउटपुट 3 होगा।

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

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

• यदि नोड का राइट चाइल्ड null नहीं है, तो:
  • node := node का राइट चाइल्ड
  • जब तक नोड का लेफ्ट चाइल्ड null नहीं है, करें:
    • node := node का लेफ्ट चाइल्ड
  • node लौटाएँ
• जब तक (नोड का पैरेंट null नहीं है और नोड अपने पैरेंट के लेफ्ट चाइल्ड के समान नहीं है), करें:
  • node := नोड का पैरेंट
• नोड के पैरेंट को लौटाएँ

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
    Node(int v, Node* par = NULL) {
        val = v;
        left = NULL;
        right = NULL;
        parent = par;
    }
};

class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        if (node->right) {
            node = node->right;
            while (node->left)
                node = node->left;
            return node;
        }
        while (node->parent && node != node->parent->left) {
            node = node->parent;
        }
        return node->parent;
    }
};

int main() {
    Solution ob;
    Node *root = new Node(5);
    root->left = new Node(3, root);
    root->right = new Node(6, root);
    root->left->left = new Node(2, root->left);
    root->left->right = new Node(4, root->left);
    root->left->left->left = new Node(1, root->left->left);
    cout << (ob.inorderSuccessor(root->left->left))->val;
    return 0;
}

इनपुट

Node *root = new Node(5); root->left = new Node(3, root); root->right = new Node(6, root); root->left->left = new Node(2, root->left); root->left->right = new Node(4, root->left); root->left->left->left = new Node(1, root->left->left); (ob.inorderSuccessor(root->left->left))->val

आउटपुट

3