C++ में BST कीज़ को दी गई रेंज में प्रिंट करना - O(1) स्पेस

इस समस्या में, हमें दो मान k1 और k2 (k1 < k2) दिए गए हैं, और बाइनरी सर्च ट्री की रूट। हमारा कार्य दी गई रेंज में BST कीज़ प्रिंट करने का प्रोग्राम बनाना है।

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

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

इनपुट:

k1 = 4, k2 = 12

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

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

सरलता से हम इनऑर्डर ट्रैवर्सल का उपयोग करके समस्या को हल कर सकते हैं लेकिन वहां स्पेस जटिलता O(n) है लेकिन आवश्यकता O(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* current = root;
   while (current) {
      if (current->left == NULL) {
         if (current->data <= k2 && current->data >= k1)
            cout << current->data << " ";
         current = current->right;
      } else {
         node* predecessor = current->left;
         while (predecessor->right != NULL && predecessor->right != current)
            predecessor = predecessor->right;
         
         if (predecessor->right == NULL) {
            predecessor->right = current;
            current = current->left;
         } else {
            predecessor->right = NULL;
            if (current->data <= k2 && current->data >= k1)
               cout << current->data << " ";
            current = current->right;
         }
      }
   }
}

int main() {
   node* root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(10);
   root->left->left = insertNode(1);
   root->left->right = insertNode(7);
   root->right->right = insertNode(9);
   
   cout << "दी गई रेंज में सभी BST कीज़ हैं: ";
   RangeTraversal(root, 4, 10);
   return 0;
}

आउटपुट

दी गई रेंज में सभी BST कीज़ हैं: 6 7 9

नोट: मूल कोड में ट्री स्ट्रक्चर और एम्परसैंड एन्कोडिंग (&amp;&amp;) की समस्याएं थीं। ऊपर सही संस्करण दिया गया है।

मॉरिस ट्रैवर्सल के लाभ

• स्पेस जटिलता: O(1) - कोई स्टैक/रिकर्सन नहीं
• समय जटिलता: O(n) - प्रत्येक एज को अधिकतम 2 बार विजिट किया जाता है
• ट्री को अस्थायी रूप से संशोधित करता है लेकिन अंत में रिस्टोर कर देता है
• थ्रेडेड बाइनरी ट्री कॉन्सेप्ट का उपयोग करता है