इस ट्यूटोरियल में, हम एक बाइनरी ट्री में पहली सबसे छोटी रूट टू लीफ पाथ को प्रिंट करने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसमें, हमें अलग-अलग मानों वाला एक बाइनरी ट्री दिया जाएगा, और हमें दिए गए बाइनरी ट्री में रूट नोड से लीफ नोड तक का सबसे छोटा रास्ता खोजना होगा।
इसे हल करने के लिए, हम एक बाइनरी ट्री में लेवल ऑर्डर ट्रैवर्सल करने के लिए कतार का उपयोग कर सकते हैं और नोड्स को सबसे छोटे पथ में स्टोर कर सकते हैं। इसके लिए, एक बार जब हम अंतिम स्तर के लिए सबसे बाएं नोड पर पहुंच जाते हैं, तो हम कतार से मान प्राप्त करते हैं और सबसे छोटा पथ प्रिंट करते हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct Node{
struct Node* left;
struct Node* right;
int data;
};
struct Node* create_node(int data){
struct Node* temp = new Node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void print_spath(int Data, unordered_map<int, int> parent){
if (parent[Data] == Data)
return;
print_spath(parent[Data], parent);
cout << parent[Data] << " ";
}
void leftmost_path(struct Node* root){
queue<struct Node*> q;
q.push(root);
int LeafData = -1;
struct Node* temp = NULL;
unordered_map<int, int> parent;
parent[root->data] = root->data;
while (!q.empty()){
temp = q.front();
q.pop();
if (!temp->left && !temp->right){
LeafData = temp->data;
break;
}
else{
if (temp->left){
q.push(temp->left);
parent[temp->left->data] = temp->data;
}
if (temp->right) {
q.push(temp->right);
parent[temp->right->data] = temp->data;
}
}
}
print_spath(LeafData, parent);
cout << LeafData << " ";
}
int main(){
struct Node* root = create_node(21);
root->left = create_node(24);
root->right = create_node(35);
root->left->left = create_node(44);
root->right->left = create_node(53);
root->right->right = create_node(71);
root->left->left->left = create_node(110);
root->left->left->right = create_node(91);
root->right->right->left = create_node(85);
leftmost_path(root);
return 0;
} आउटपुट
21 35 53