इस समस्या में, हमें एक बाइनरी ट्री बीटी और एक प्रमुख मूल्य दिया जाता है। हमारा काम किसी दिए गए कुंजी का अगला दायां नोड ढूंढना है।
बाइनरी ट्री एक विशेष डेटा संरचना है जिसका उपयोग डेटा संग्रहण उद्देश्यों के लिए किया जाता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
key = 4
आउटपुट
5
स्पष्टीकरण
नोड 4 के आगे का तत्व 5 है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान बाइनरी ट्री को लेवल ऑर्डर ट्रैवर्सल का उपयोग करके ट्रैवर्स करना है। और दिए गए कुंजी मान के लिए, हम जांच करेंगे कि क्या ट्रैवर्सल में समान स्तर पर नोड के बगल में कोई नोड मौजूद है। यदि हाँ, तो अगला नोड लौटाएँ, अन्यथा NULL लौटाएँ।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <iostream>
#include <queue>
using namespace std;
struct node {
struct node *left, *right;
int key;
};
node* newNode(int key) {
node *temp = new node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
node* findNextRightNodeBT(node *root, int k) {
if (root == NULL)
return 0;
queue<node *> nodeVal;
queue<int> nodeLevel;
int level = 0;
nodeVal.push(root);
nodeLevel.push(level);
while (nodeVal.size()) {
node *node = nodeVal.front();
level = nodeLevel.front();
nodeVal.pop();
nodeLevel.pop();
if (node->key == k) {
if (nodeLevel.size() == 0 || nodeLevel.front() != level)
return NULL;
return nodeVal.front();
}
if (node->left != NULL) {
nodeVal.push(node->left);
nodeLevel.push(level+1);
}
if (node->right != NULL) {
nodeVal.push(node->right);
nodeLevel.push(level+1);
}
}
return NULL;
}
int main() {
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
int key = 4;
cout<<"The next right node of the node "<<key<<" is ";
node *nextNode = findNextRightNodeBT(root, key);
if(nextNode != NULL)
cout<<nextNode->key;
else
cout<<"not available";
return 0;
} आउटपुट
The next right node of the node 4 is 5