सी ++ में बीएसटी II में उत्तराधिकारी उत्तराधिकारी

मान लीजिए कि हमारे पास बाइनरी सर्च ट्री में एक नोड है, हमें बीएसटी में उस नोड के इन-ऑर्डर उत्तराधिकारी को खोजना होगा। यदि कोई इन-ऑर्डर उत्तराधिकारी नहीं है, तो अशक्त लौटें। जैसा कि हम जानते हैं कि नोड का उत्तराधिकारी वह नोड होता है जिसकी कुंजी नोड के मान से अधिक होती है।

हमारे पास नोड तक सीधी पहुंच होगी लेकिन पेड़ की जड़ तक नहीं। यहां प्रत्येक नोड के पास उसके मूल नोड का संदर्भ होगा। नीचे नोड की परिभाषा दी गई है -

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

अगर इनपुट इस तरह है -

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

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

• यदि नोड का दायां शून्य नहीं है, तो -

  • नोड:=नोड के दाईं ओर

  • जबकि नोड का बायां भाग शून्य नहीं है, करें -

    • नोड :=नोड के बाईं ओर

  • वापसी नोड

• जबकि (नोड का पैरेंट अशक्त नहीं है और नोड नोड के पैरेंट के बाएं के बराबर नहीं है), करें -

  • नोड:=नोड का जनक

• वापसी नोड के जनक

उदाहरण

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

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

इनपुट

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