इस समस्या में, हमें एक बाइनरी ट्री दी गई है और हमें बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना है।
उदाहरण
इनपुट -

आउटपुट - 7 4 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->left = temp->right = NULL;
return temp;
}
void findLeafNode(Node* root) {
if (!root)
return;
if (!root->left && !root->right) {
cout << root->data << "\t";
return;
}
if (root->right)
findLeafNode(root->right);
if (root->left)
findLeafNode(root->left);
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(8);
cout << "Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}
आउटपुट
Leaf nodes of the tree from right to left are - 18 2 98 8
पोस्टऑर्डर ट्रैवर्सल
लीफ नोड ढूंढने के लिए यह ट्रैवर्सल इटरेशन का उपयोग करेगा। हम डेटा संग्रहीत करने के लिए एक स्टैक का उपयोग करेंगे और ट्री को पोस्टऑर्डर तरीके से पार करेंगे (पहले दायां सबट्री फिर बायां सबट्री और फिर रूट) और लीफ नोड्स प्रिंट करेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम:
#include<bits/stdc++.h>
using namespace std;
struct Node {
Node* left;
Node* right;
int data;
};
Node* insertNode(int key) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
void findLeafNode(Node* tree) {
stack<Node*> treeStack;
while (1) {
if (tree) {
treeStack.push(tree);
tree = tree->right;
} else {
if (treeStack.empty())
break;
else {
if (treeStack.top()->left == NULL) {
tree = treeStack.top();
treeStack.pop();
if (tree->right == NULL)
cout << tree->data << "\t";
}
while (tree == treeStack.top()->left) {
tree = treeStack.top();
treeStack.pop();
if (treeStack.empty())
break;
}
if (!treeStack.empty())
tree = treeStack.top()->left;
else
tree = NULL;
}
}
}
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(18);
cout << "Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}
आउटपुट
Leaf nodes of the tree from right to left are - 18 2 98 8