इस समस्या में, हमें एक बाइनरी सर्च ट्री के दो नोड दिए जाते हैं। और हमें पेड़ में होने वाले k1 से k2 की सीमा में सभी मानों को प्रिंट करना होगा। यानी हमें k1 से बड़े और k2 से छोटे सभी मानों को प्रिंट करना होगा। और हमें इन सभी चाबियों को उनके मूल्यों के बढ़ते क्रम में प्रिंट करना होगा।
बाइनरी सर्च ट्री एक पेड़ है जो इन 3 गुणों का पालन करता है -
-
लेफ्ट सबट्री में नोड के मान से कम मान वाले नोड होते हैं।
-
दाएँ उपट्री में एक नोड होता है जिसका मान नोड के मान से अधिक होता है।
-
एक उपट्री का भी एक बाइनरी सर्च ट्री होना चाहिए। ट्री में किसी डुप्लीकेट नोड की अनुमति नहीं है।
उदाहरण ,
आइए विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं,
Input : k1 = 12 and k2 = 25. Output : 15, 20, 24
पेड़ -
स्पष्टीकरण - पेड़ को पार करने पर, सभी तत्वों का पता लगाया जाएगा और जो तत्व 12 से 25 की सीमा के बीच हैं, यानी नोड x के लिए, 12 x ≥ 25 मुद्रित किया जाएगा।
यहां, हम अपना समाधान खोजने के लिए बीएसटी के गुणों का उपयोग करेंगे। यानी लेफ्ट सबट्री में सभी एलिमेंट रूट से छोटे होते हैं और राइट सबट्री में सभी एलिमेंट रूट नोड से बड़े होते हैं। और हम इस समस्या को हल करने के लिए बीएसटी के क्रम में उपयोग करेंगे। अब, इस समस्या को हल करने के लिए एक एल्गोरिथम बनाते हैं।
एल्गोरिदम
Step 1 : Compare the root node with the k1 and k2. Step 2 : If root is greater than k1. Call left subtree for the search recursively. Step 3 : If root is smaller than k2. Call right subtree for the search recursively. Step 4 : If the root of the tree is in the range. Then print the root’s value.
उदाहरण
अब, इस एल्गोरिथम के आधार पर, समस्या को हल करने के लिए एक प्रोग्राम बनाते हैं।
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
};
void nodesInRange(node *root, int k1, int k2){
if ( NULL == root )
return;
if ( k1 < root->data )
nodesInRange(root->left, k1, k2);
if ( k1 <= root->data && k2 >= root->data )
cout<<root->data<<"\t";
if ( k2 > root->data )
nodesInRange(root->right, k1, k2);
}
node* insert(int data){
node *temp = new node();
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int main(){
node *root = new node();
int k1 = 12, k2 = 25;
root = insert(20);
root->left = insert(10);
root->right = insert(24);
root->left->left = insert(8);
root->left->right = insert(15);
root->right->right = insert(32);
cout<<”The values of node within the range are\t”;
nodesInRange(root, k1, k2);
return 0;
} आउटपुट
The values of node within the range are 15 20 24.