C++ में बाइनरी ट्री में K लीफ वाले सभी नोड्स प्रिंट करना

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

बाइनरी ट्री

बाइनरी ट्री एक विशेष ट्री है जिसके प्रत्येक नोड में अधिकतम दो नोड्स होते हैं (एक/दो/कोई नहीं)।

लीफ नोड

बाइनरी ट्री का लीफ नोड ट्री के अंत में स्थित नोड है।

उदाहरण

K = 2

आउटपुट - {S}

इस समस्या को हल करने के लिए, हम ट्री के लिए पोस्टऑर्डर ट्रैवर्सल करेंगे। अब, हम प्रत्येक बाएं सबट्री और दाएं सबट्री को देखेंगे यदि लीफ का योग K है, तो वर्तमान नोड प्रिंट करें अन्यथा रिकर्सिवली कॉल करें, सबट्री के लीफ काउंट।

यह समाधान ट्रैवर्सल पर आधारित है इसलिए कॉम्प्लेक्सिटी ट्री के आकार के क्रम की होगी। टाइम कॉम्प्लेक्सिटी - O(n)

उदाहरण

उपरोक्त दृष्टिकोण को लागू करने वाला प्रोग्राम:

#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 are :\n"; 
    nodeWithKLeave(root, K); 
    return 0; 
}

आउटपुट

Nodes with 2 leaves are: N T