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

আউটপুট

Nodes with 2 leaves are: N T