C++ में दिए गए नोड से दूरी K पर सभी नोड्स प्रिंट करना

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

बाइनरी ट्री

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

उदाहरण

K = 2

टारगेट नोड: 9

आउटपुट -

5 1 3

व्याख्या -

दूरी नोड से ऊपर, नीचे या उसी लेवल पर ली जा सकती है। इसलिए, हम तदनुसार नोड्स लौटाएंगे।

इस समस्या को हल करने के लिए हमें यह समझना होगा कि टारगेट नोड से K दूरी पर किस प्रकार के नोड्स होते हैं।

उपरोक्त उदाहरण से, हम देख सकते हैं कि K दूर के नोड्स टारगेट नोड के सबट्री में हो सकते हैं (5 और 1) या टारगेट नोड के पूर्वजों के सबट्री में कहीं भी (3)।

पहले केस का समाधान खोजने की विधि टारगेट नोड के सबट्री को पार करके और जांचना है कि क्या किसी नोड की टारगेट से दूरी K है। यदि हां तो नोड प्रिंट करें।

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

उदाहरण

नीचे दिया गया प्रोग्राम हमारे समाधान का कार्यान्वयन दिखाएगा:

#include <iostream> 
using namespace std; 

struct node { 
    int data; 
    struct node *left, *right; 
}; 

void printSubtreeNodes(node *root, int k) { 
    if (root == NULL || k < 0) return; 
    if (k == 0) { 
        cout << root->data << "\t"; 
        return; 
    } 
    printSubtreeNodes(root->left, k-1); 
    printSubtreeNodes(root->right, k-1); 
} 

int printKNodes(node* root, node* target, int k) { 
    if (root == NULL) return -1; 
    if (root == target) { 
        printSubtreeNodes(root, k); 
        return 0; 
    } 
    int dl = printKNodes(root->left, target, k); 
    if (dl != -1) { 
        if (dl + 1 == k) 
            cout << root->data << "\t"; 
        else 
            printSubtreeNodes(root->right, k-dl-2); 
        return 1 + dl; 
    } 
    int dr = printKNodes(root->right, target, k); 
    if (dr != -1) { 
        if (dr + 1 == k) 
            cout << root->data << endl; 
        else 
            printSubtreeNodes(root->left, k-dr-2); 
        return 1 + dr; 
    } 
    return -1; 
} 

node *insertNode(int data) { 
    node *temp = new node; 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 

int main() { 
    node *root = insertNode(6); 
    root->left = insertNode(3); 
    root->right = insertNode(9); 
    root->left->right = insertNode(4); 
    root->right->left = insertNode(8); 
    root->right->right = insertNode(10); 
    root->right->right->left = insertNode(5); 
    root->right->right->right = insertNode(1); 
    node *target = root->right; 
    int K = 2; 
    cout << "Nodes at distance " << K << " from the target node are :\n"; 
    printKNodes(root, target, K); 
    return 0; 
}

आउटपुट

Nodes at distance 2 from the target node are - 5 1 3