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

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

बाइनरी ट्री

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

लीफ नोड

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

इस समस्या में, लीफ नोड से दूरी का अर्थ उस नोड से है जो लीफ नोड से उच्च लेवल पर है। मान लीजिए, लेवल 4 पर स्थित लीफ नोड से दूरी 2 पर स्थित नोड लेवल 2 पर होगा।

उदाहरण

K = 2

आउटपुट - 6 9

इस समस्या को हल करने के लिए, हम ट्री को पार करेंगे। सभी पैरेंट नोड सेट्स (जिन्हें पूर्वज नोड्स भी कहा जाता है) को लेवल दर लेवल संग्रहीत करेंगे जब तक लीफ नोड नहीं पहुंच जाता। अब, हम लीफ नोड से k दूरी पर स्थित पूर्वज को प्रिंट करेंगे। ट्रैवर्सल के दौरान विज़िटेड नोड्स को मार्क करना डुप्लिकेट से बचने के लिए महत्वपूर्ण है और हम इसके लिए बूलियन ऐरे का उपयोग करेंगे।

चूंकि कोड केवल ट्री ट्रैवर्सल का उपयोग करता है, कॉम्प्लेक्सिटी n के समानुपाती है। टाइम कॉम्प्लेक्सिटी: O(n)

उदाहरण

हमारे तर्क को दर्शाने वाला प्रोग्राम:

#include <iostream> 
using namespace std; 

#define MAX_HEIGHT 10000 

struct Node { 
    int key; 
    Node *left, *right; 
}; 

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

void nodesKatDistance(Node* node, int path[], bool visited[], int pathLen, int k) { 
    if (node == NULL) return; 
    path[pathLen] = node->key; 
    visited[pathLen] = false; 
    pathLen++; 
    if (node->left == NULL && node->right == NULL && pathLen - k - 1 >= 0 && visited[pathLen - k - 1] == false) { 
        cout << path[pathLen - k - 1] << "\t"; 
        visited[pathLen - k - 1] = true; 
        return; 
    } 
    nodesKatDistance(node->left, path, visited, pathLen, k); 
    nodesKatDistance(node->right, path, visited, pathLen, k); 
} 

void printNodes(Node* node, int k) { 
    int path[MAX_HEIGHT]; 
    bool visited[MAX_HEIGHT] = {false}; 
    nodesKatDistance(node, path, visited, 0, k); 
} 

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->left->left = insertNode(5); 
    root->right->left->right = insertNode(1); 
    int k = 2; 
    cout << "All nodes at distance " << k << " from leaf node are:\n"; 
    printNodes(root, k); 
    return 0; 
}

आउटपुट

All nodes at distance 2 from the leaf node are -

6 9