এই সমস্যায়, আমাদেরকে একটি বাইনারি ট্রি এবং একটি সংখ্যা 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;
} আউটপুট
লিফ নোড থেকে 2 দূরত্বের সমস্ত নোড হল −
6 9
