C++ में बाइनरी ट्री के दो नोड्स के बीच दूरी ढूंढना

इस समस्या में, हमें एक बाइनरी ट्री और दो नोड्स दिए गए हैं। हमारा कार्य बाइनरी ट्री के दो नोड्स के बीच दूरी ढूंढने के लिए एक प्रोग्राम बनाना है।

समस्या विवरण

हमें दो नोड्स के बीच की दूरी ढूंढनी है जो एक नोड से दूसरे नोड तक जाने पर पार की जाने वाली न्यूनतम एज की संख्या है।

उदाहरण से समझते हैं

इनपुट: बाइनरी ट्री

Node1 = 3, Node2 = 5

आउटपुट: 3

व्याख्या

नोड 3 से नोड 5 तक का पथ 3 → 1 → 2 → 5 है। 3 एज पार की गई हैं जो दूरी 3 बनाती हैं।

समाधान दृष्टिकोण

समस्या का एक सरल समाधान दिए गए नोड्स के लिए निम्नतम सामान्य पूर्वज (LCA) नोड का उपयोग करना और फिर नीचे दिए गए सूत्र को लागू करना है,

distance(node1, node2) = distance(root, node1) + distance(root, node2) - 2 * distance(root, LCA)

C++ प्रोग्राम उदाहरण

#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