मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें रूट और दूसरे नोड 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
