এই সমস্যায়, আমাদের একটি বাইনারি গাছ এবং দুটি নোড দেওয়া হয়। আমাদের কাজ হল একটি বাইনারি ট্রির দুটি নোডের মধ্যে দূরত্ব খোঁজার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমাদের দুটি নোডের মধ্যে দূরত্ব খুঁজে বের করতে হবে যা প্রান্তের ন্যূনতম সংখ্যা যা আমরা যখন একটি নোড থেকে অন্য নোডে যাই তখন অতিক্রম করা হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট :বাইনারি গাছ
Node1 =3 ,Node2 =5
আউটপুট :3
ব্যাখ্যা
নোড 3 থেকে নোড 5 পর্যন্ত পথটি হল 3 -> 1 -> 2 -> 5। এখানে 3টি প্রান্ত রয়েছে যা 3টি দূরত্ব তৈরি করে৷
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল প্রদত্ত নোডগুলির জন্য সর্বনিম্ন সাধারণ পূর্বপুরুষ নোড ব্যবহার করা এবং তারপরে নীচের সূত্রটি প্রয়োগ করুন,
দূরত্ব(নোড১, নোড২) =দূরত্ব(মূল, নোড১) + দূরত্ব(মূল, নোড২) + দূরত্ব(মূল, এলসিএ)
উদাহরণ
#include <iostream>
using namespace std;
struct Node{
struct Node *left, *right;
int key;
};
Node* insertNode(int key){
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
int calcNodeLevel(Node *root, int val, int level) {
if (root == NULL)
return -1;
if (root->key == val)
return level;
int lvl = calcNodeLevel(root->left, val, level+1);
return (lvl != -1)? lvl : calcNodeLevel(root->right, val, level+1);
}
Node *findDistanceRec(Node* root, int node1, int node2, int &dist1, int &dist2, int &dist, int lvl){
if (root == NULL) return NULL;
if (root->key == node1){
dist1 = lvl;
return root;
}
if (root->key == node2){
dist2 = lvl;
return root;
}
Node *leftLCA = findDistanceRec(root->left, node1, node2, dist1,dist2, dist, lvl+1);
Node *rightLCA = findDistanceRec(root->right, node1, node2, dist1,dist2, dist, lvl+1);
if (leftLCA && rightLCA){
dist = dist1 + dist2 - 2*lvl;
return root;
}
return (leftLCA != NULL)? leftLCA: rightLCA;
}
int CalcNodeDistance(Node *root, int node1, int node2) {
int dist1 = -1, dist2 = -1, dist;
Node *lca = findDistanceRec(root, node1, node2, dist1, dist2, dist, 1);
if (dist1 != -1 && dist2 != -1)
return dist;
if (dist1 != -1){
dist = calcNodeLevel(lca, node2, 0);
return dist;
}
if (dist2 != -1){
dist = calcNodeLevel(lca, node1, 0);
return dist;
}
return -1;
}
int main(){
Node * root = insertNode(1);
root->left = insertNode(2);
root->right = insertNode(3);
root->left->left = insertNode(4);
root->left->right = insertNode(5);
root->right->left = insertNode(6);
cout<<"Distance between node with value 5 and node with value 3 is"<<CalcNodeDistance(root, 3, 5);
return 0;
} আউটপুট
Distance between node with value 5 and node with value 3 is 3
