ধরুন, একটি বাইনারি গাছ দেওয়া হয়েছে। এটির বিভিন্ন স্তরে লিফ নোড রয়েছে। আরেকটি পয়েন্টার দেওয়া হয়, যে একটি নোড নির্দেশ করা হয়. আমাদের পয়েন্টেড নোড থেকে নিকটতম লিফ নোডের দূরত্ব খুঁজে বের করতে হবে। বিবেচনা করুন গাছটি নীচের মত -
এখানে লিফ নোডগুলি হল 2, -2 এবং 6৷ যদি পয়েন্টারটি নোড -5 এর দিকে নির্দেশ করে, তবে -5 থেকে সবচেয়ে কাছের নোডগুলি হবে 1 দূরত্বে৷
এটি সমাধান করার জন্য, আমরা প্রদত্ত নোডের সাথে শিকড়যুক্ত উপবৃক্ষটি অতিক্রম করব এবং উপবৃক্ষের নিকটতম পাতাটি খুঁজে বের করব, তারপর দূরত্বটি সংরক্ষণ করব। এখন রুট থেকে শুরু করে ট্র্যাভার্সিং ট্রি, যদি বাম সাবট্রিতে নোড x থাকে, তাহলে ডান সাবট্রিতে অনুসন্ধান করুন এবং এর বিপরীতে।
উদাহরণ
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
void getLeafDownward(Node *root, int level, int *minDist) {
if (root == NULL)
return ;
if (root->left == NULL && root->right == NULL) {
if (level < (*minDist))
*minDist = level;
return;
}
getLeafDownward(root->left, level+1, minDist);
getLeafDownward(root->right, level+1, minDist);
}
int getFromParent(Node * root, Node *x, int *minDist) {
if (root == NULL)
return -1;
if (root == x)
return 0;
int l = getFromParent(root->left, x, minDist);
if (l != -1) {
getLeafDownward(root->right, l+2, minDist);
return l+1;
}
int r = getFromParent(root->right, x, minDist);
if (r != -1) {
getLeafDownward(root->left, r+2, minDist);
return r+1;
}
return -1;
}
int minimumDistance(Node *root, Node *x) {
int minDist = INT8_MAX;
getLeafDownward(x, 0, &minDist);
getFromParent(root, x, &minDist);
return minDist;
}
int main() {
Node* root = getNode(4);
root->left = getNode(2);
root->right = getNode(-5);
root->right->left = getNode(-2);
root->right->right = getNode(6);
Node *x = root->right;
cout << "Closest distance of leaf from " << x->data <<" is: " << minimumDistance(root, x);
} আউটপুট
Closest distance of leaf from -5 is: 1
