C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें

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

यहां लीफ नोड्स 2, -2 और 6 हैं। यदि पॉइंटर नोड -5 पर इंगित कर रहा है, तो -5 से निकटतम नोड्स दूरी 1 पर होंगे।

इसे हल करने के लिए, हम दिए गए नोड के साथ रूटेड सबट्री को पार करेंगे, और सबट्री में निकटतम लीफ ढूंढेंगे, फिर दूरी स्टोर करेंगे। अब रूट से शुरू करके ट्री को पार करें, यदि नोड x बाएं सबट्री में मौजूद है, तो दाएं सबट्री में खोजें, और इसके विपरीत।

उदाहरण

#include 
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;
}

void getLeafDownward(Node *root, int level, int *minDist) {
    if (root == NULL)
        return ;
    if (root->left == NULL && root->right == NULL) {
        if (level < (*minDist))
            *minDist = level;
        return;
    }
    getLeafDownward(root->left, level+1, minDist);
    getLeafDownward(root->right, level+1, minDist);
}

int getFromParent(Node * root, Node *x, int *minDist) {
    if (root == NULL)
        return -1;
    if (root == x)
        return 0;
    int l = getFromParent(root->left, x, minDist);
    if (l != -1) {
        getLeafDownward(root->right, l+2, minDist);
        return l+1;
    }
    int r = getFromParent(root->right, x, minDist);
    if (r != -1) {
        getLeafDownward(root->left, r+2, minDist);
        return r+1;
    }
    return -1;
}

int minimumDistance(Node *root, Node *x) {
    int minDist = INT8_MAX;
    getLeafDownward(x, 0, &minDist);
    getFromParent(root, x, &minDist);
    return minDist;
}

int main() {
    Node* root = getNode(4);
    root->left = getNode(2);
    root->right = getNode(-5);
    root->right->left = getNode(-2);
    root->right->right = getNode(6);
    Node *x = root->right;
    cout << "Closest distance of leaf from " << x->data << " is: " << minimumDistance(root, x);
}

आउटपुट

Closest distance of leaf from -5 is: 1