इस समस्या में, हमें एक बाइनरी ट्री और एक नंबर K दिया जाता है। हमें ट्री के सभी नोड्स को प्रिंट करना होता है जो लीफ नोड से k दूरी पर होते हैं।
बाइनरी ट्री एक विशेष पेड़ है जिसके प्रत्येक नोड में अधिकतम दो नोड (एक/दो/कोई नहीं) होते हैं।
लीफ नोड बाइनरी ट्री का नोड ट्री के अंत में होता है।
इस समस्या में लीफ नोड से दूरी लीफ नोड की तुलना में उच्च स्तर पर नोड होती है। मान लीजिए, स्तर 4 पर लीफ नोड से दूरी 2 पर नोड स्तर 2 पर होगा।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं
के =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;
} आउटपुट
लीफ नोड से दूरी 2 पर सभी नोड्स हैं -
6 9