मान लें कि हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें रूट और दूसरे नोड u के बीच की दूरी का पता लगाना है। मान लीजिए पेड़ नीचे जैसा है:
अब बीच की दूरी (रूट, 6) =2, पथ की लंबाई 2, के बीच की दूरी (रूट, 8) =3 आदि।
इस समस्या को हल करने के लिए, हम बाएँ और दाएँ सबट्री में नोड को खोजने के लिए एक पुनरावर्ती दृष्टिकोण का उपयोग करेंगे, और प्रत्येक स्तर के लिए लंबाई को भी अपडेट करेंगे।
उदाहरण
#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;
}
int getDistance(Node *root, int x) {
if (root == NULL)
return -1;
int dist = -1;
if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)
return dist + 1;
return dist;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
cout <<"Distance from root to node 6 is: " << getDistance(root,6);
cout << "\nDistance from root to node 8 is: " << getDistance(root,8);
} आउटपुट
Distance from root to node 6 is: 2 Distance from root to node 8 is: 3