বাইনারি ট্রিতে নিকটতম লিফ নোড খুঁজে বের করা (C++)

একটি বাইনারি ট্রি এবং একটি নোড X দেওয়া আছে। X থেকে নিকটতম লিফ নোডের দূরত্ব বের করতে হবে।

অ্যালগরিদম: X-র সাবট্রিতে নিকটতম লিফ খুঁজুন। তারপর রুট থেকে X-র পথ ফলো করে অন্য সাবট্রিতে লিফ খুঁজুন। ন্যূনতম দূরত্ব রিটার্ন করুন।

উদাহরণ

#include <iostream>
#include <climits>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
};

Node* getNode(int data) {
    Node* n = new Node;
    n->data = data; n->left = n->right = NULL;
    return n;
}

void getLeafDownward(Node* root, int level, int* minDist) {
    if (!root) return;
    if (!root->left && !root->right) {
        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) 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 = INT_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);
    return 0;
}

আউটপুট

Closest distance of leaf from -5 is: 1