इस समस्या में, हमें एक बाइनरी ट्री और एक पूर्णांक K दिया जाता है और हमें बाइनरी ट्री के उन सभी नोड्स को प्रिंट करना होता है जिनके चाइल्ड सबट्री में K पत्ते होते हैं।
बाइनरी ट्री एक विशेष पेड़ है जिसके प्रत्येक नोड में अधिकतम दो नोड (एक/दो/कोई नहीं) होते हैं।
लीफ नोड बाइनरी ट्री का नोड ट्री के अंत में होता है।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -
के =2
आउटपुट - {एस}
इस समस्या को हल करने के लिए हम पेड़ के लिए ट्रैवर्सल (पोस्टऑर्डर) करेंगे। अब, यदि पत्तियों का योग K है, तो हम प्रत्येक बाएँ उप-वृक्ष और दाएँ उपप्रकार देखेंगे, वर्तमान नोड प्रिंट करें अन्यथा रिकर्सिवली कॉल करें, सबट्री की पत्तियों की गिनती होती है।
यह समाधान ट्रैवर्सिंग पर आधारित है इसलिए जटिलता पेड़ के आकार के क्रम की होगी। समय की जटिलता - ओ(एन)
उदाहरण
उपरोक्त दृष्टिकोण को लागू करने का कार्यक्रम
#include<bits/stdc++.h>
using namespace std;
struct Node{
char data ;
struct Node * left, * right ;
};
struct Node * insertNode(char data){
struct Node * node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int nodeWithKLeave(struct Node *ptr,int k){
if (ptr == NULL)
return 0;
if (ptr->left == NULL && ptr->right == NULL)
return 1;
int total = nodeWithKLeave(ptr->left, k) + nodeWithKLeave(ptr->right, k);
if (k == total)
cout<<ptr->data<<" ";
return total;
}
int main() {
struct Node *root = insertNode('A');
root->left = insertNode('B');
root->right = insertNode('K');
root->left->left = insertNode('N');
root->left->right = insertNode('S');
root->left->left->left = insertNode('X');
root->left->left->right = insertNode('H');
root->right->right = insertNode('E');
root->right->left = insertNode('T');
root->right->left->left = insertNode('O');
root->right->left->right = insertNode('P');
int K = 2;
cout<<"Nodes with "<<K<<" leaves is :\n";
nodeWithKLeave(root, K);
return 0;
} आउटपुट
Nodes with 2 leaves are: N T