इस समस्या में, हमें एक बाइनरी ट्री और ट्री में दो लेवल दिए गए हैं (ऊपरी और निचला) और हमें ट्री के ऊपरी और निचले लेवल के बीच के सभी नोड्स प्रिंट करने हैं।
बाइनरी ट्री
बाइनरी ट्री एक विशेष ट्री है जिसके प्रत्येक नोड में अधिकतम दो नोड्स होते हैं (एक/दो/कोई नहीं)।
उदाहरण
ऊपरी - 1
निचला - 3
आउटपुट -
6 3 9 7 4 8 10
इस समस्या को हल करने के लिए, हमें ट्री के दिए गए लेवल पर नोड्स प्रिंट करने होंगे। हम ऊपरी से निचला लेवल तक ट्री में लूप का उपयोग करके एक रिकर्सिव फंक्शन कॉल करेंगे।
यह एल्गोरिदम सरल है लेकिन n² क्रम की अधिक कॉम्प्लेक्सिटी है।
एक अधिक प्रभावी समाधान इनऑर्डर ट्रैवर्सल और कतार का उपयोग करके करना है। और दिए गए ऊपरी और निचले लेवल के भीतर नोड्स प्रिंट करना।
उदाहरण
हमारे समाधान को लागू करने वाला प्रोग्राम:
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int key;
struct Node* left, *right;
};
void printNodesAtLevel(Node* root, int low, int high) {
queue<Node *> Q;
Node *marker = new Node;
int level = 1;
Q.push(root);
Q.push(marker);
while (Q.empty() == false) {
Node *n = Q.front();
Q.pop();
if (n == marker) {
cout << endl;
level++;
if (Q.empty() == true || level > high) break;
Q.push(marker);
continue;
}
if (level >= low)
cout << n->key << " ";
if (n->left != NULL) Q.push(n->left);
if (n->right != NULL) Q.push(n->right);
}
}
Node* insertNode(int key) {
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
int main() {
struct Node *root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(9);
root->left->left = insertNode(7);
root->left->right = insertNode(4);
root->left->right->left = insertNode(8);
root->left->right->right = insertNode(10);
root->left->right->right->left = insertNode(5);
root->left->right->right->right = insertNode(1);
root->left->right->left->left = insertNode(14);
root->left->right->left->right = insertNode(26);
int upper = 3;
int lower = 1;
cout << "Level wise Nodes between level " << lower << " and " << upper << " are \n";
printNodesAtLevel(root, lower, upper);
return 0;
}
आउटपुट
Level wise Nodes between level 1 and 3 are 6 3 9 7 4
