दिए गए रेंज में BST कुंजियाँ प्रिंट करें - O(1) C++ में स्थान

इस समस्या में, हमें दो मान k1 और k2 (k1 दी गई रेंज में BST कुंजियाँ प्रिंट करें।

समस्या का विवरण: हम पेड़ की सभी चाबियों को n1 से n2 तक बढ़ते क्रम में प्रिंट करेंगे।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट:

<मजबूत>

k1 =4, k2 =12

आउटपुट: 6, 7, 9

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

सरल हम इनऑर्डर ट्रैवर्सल . का उपयोग करके समस्या का समाधान कर सकते हैं लेकिन अंतरिक्ष जटिलता 0 (एन) है लेकिन ओ (1) जटिलता में हल करना समय की आवश्यकता है। तो, इसके लिए हम एक विशेष प्रकार की ट्रैवर्सल तकनीक का प्रयोग करेंगे।

हम मॉरिस ट्रैवर्सल . का उपयोग करेंगे जो थ्रेडेड बाइनरी ट्री पर आधारित है। इसे किसी स्टैक/कतार की आवश्यकता नहीं है और जानकारी को स्टोर करने के लिए NULL पॉइंटर्स का उपयोग करता है, इससे स्टोरेज को O(1) तक कम करने में मदद मिलती है।

समस्या को हल करने के लिए मॉरिस ट्रैवर्सल की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#include <iostream>
using namespace std;

struct node {
   int data;
   struct node *left, *right;
};

node* insertNode(int data) {
   node* temp = new node;
   temp->data = data;
   temp->right = temp->left = NULL;
   return temp;
}

void RangeTraversal(node* root, int k1, int k2) {
   
   if (!root)
      return;
     
   node* nodeTraversal = root;

   while (nodeTraversal) {

      if (nodeTraversal->left == NULL) {

         if (nodeTraversal->data <= k2 &amp;&amp; nodeTraversal->data >= k1)
         
            cout<<nodeTraversal->data<<" ";
         nodeTraversal = nodeTraversal->right;
      }

      else {
         node* prevNode = nodeTraversal->left;
         while (prevNode->right != NULL &amp;&amp; prevNode->right != nodeTraversal)
            prevNode = prevNode->right;

         if (prevNode->right == NULL) {
            prevNode->right = nodeTraversal;
            nodeTraversal = nodeTraversal->left;
         }
         else {
            prevNode->right = NULL;
            if (nodeTraversal->data <= k2 &amp;&amp; nodeTraversal->data >= k1)
               cout<<nodeTraversal->data<<" ";
            nodeTraversal = nodeTraversal->right;
         }
      }
   }
}

int main() {
   node* root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(2);
   root->left->left = insertNode(1);
   root->left->right = insertNode(7);
   root->right->right = insertNode(9);

   cout<<"All BST keys in the given range are \t";
   RangeTraversal(root, 4, 10);
   
   return 0;
}

आउटपुट

All BST keys in the given range are 7 6 9