এই সমস্যায় একটি বাইনারি ট্রি, একটি টার্গেট নোড এবং একটি পূর্ণসংখ্যা 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
