इस समस्या में हमें एक बाइनरी ट्री और दो नोड दिए जाते हैं। हमारा काम बाइनरी ट्री के दो नोड्स के बीच की दूरी का पता लगाने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण
हमें दो नोड्स के बीच की दूरी को खोजने की जरूरत है जो कि किनारों की न्यूनतम संख्या है जो एक नोड से दूसरे नोड में जाने पर ट्रैवर्स की जाएगी।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :बाइनरी ट्री
Node1 =3 ,Node2 =5
आउटपुट :3
स्पष्टीकरण
नोड 3 से नोड 5 तक का पथ 3 -> 1 -> 2 -> 5 है। 3 किनारों को पार किया जाता है जो दूरी 3 बनाते हैं।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान दिए गए नोड्स के लिए सबसे कम सामान्य पूर्वज नोड का उपयोग करना है और फिर नीचे दिए गए सूत्र को लागू करना है,
दूरी (नोड 1, नोड 2) =दूरी (रूट, नोड 1) + दूरी (रूट, नोड 2) + दूरी (रूट, एलसीए)
उदाहरण
#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