এই সমস্যায়, আমাদেরকে একটি বাইনারি ট্রি, একটি টার্গেট নোড এবং একটি পূর্ণসংখ্যা 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 n tode are − 5 1 3
