এই সমস্যায় একটি বাইনারি ট্রি এবং একটি সংখ্যা K দেওয়া আছে। আমাদের ট্রির যেসব নোড লিফ নোড থেকে k দূরত্বে আছে সেগুলো প্রিন্ট করতে হবে।
বাইনারি ট্রি হলো একটি বিশেষ ট্রি যেটির প্রতিটি নোডে সর্বোচ্চ দুটি নোড থাকে (একটি/দুটো/কোনোটিই নেই)।
বাইনারি ট্রির লিফ নোড হলো ট্রির শেষে থাকা নোড।
এই সমস্যাতে লিফ নোড থেকে দূরত্ব বলতে লিফ নোডের চেয়ে উঁচু লেভেলের নোডকে বোঝায়। মনে করুন, লেভেল ৪-এর লিফ নোড থেকে দূরত্ব ২-এর নোড লেভেল ২-তে থাকবে।
উদাহরণ
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
