মনে করুন আমাদের কিছু নোডসহ একটি বাইনারি ট্রি আছে। আমাদের রুট এবং অন্য একটি নোড u-এর মধ্যে দূরত্ব বের করতে হবে। মনে করুন ট্রিটি নিচের মতো -
এখন (root, 6)-এর দূরত্ব = 2, পথের দৈর্ঘ্য 2, (root, 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
