C++ प्रोग्राम: बाइनरी सर्च ट्री में लोएस्ट कॉमन एंसेस्टर ढूंढना

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

एल्गोरिदम

शुरुआत
    डेटा d, लेफ्ट चाइल्ड पॉइंटर l और राइट चाइल्ड पॉइंटर r घोषित करने के लिए n स्ट्रक्चर बनाएं
    नया नोड बनाने के लिए फ़ंक्शन बनाएं
    बाइनरी ट्री में लोएस्ट कॉमन एंसेस्टर ढूंढने के लिए LCA() फ़ंक्शन कॉल करें:
        मान लें नोड n1 और n2 ट्री में मौजूद हैं
        यदि रूट नल है, तो लौटाएं
        यदि रूट नल नहीं है तो दो केस हैं:
            a) यदि n1 और n2 दोनों रूट से छोटे हैं, तो LCA लेफ्ट में है
            b) यदि n1 और n2 दोनों रूट से बड़े हैं, तो LCA राइट में है
समाप्ति

उदाहरण कोड

#include <iostream>
using namespace std;

struct n {
    int d;
    struct n* l, *r;
}*p = NULL;

struct n* newnode(int d) {
    p = new n;
    p->d = d;
    p->l = p->r = NULL;
    return p;
}

struct n* LCA(struct n* root, int n1, int n2) {
    if (root == NULL)
        return NULL;
    if (root->d > n1 && root->d > n2)
        return LCA(root->l, n1, n2);
    if (root->d < n1 && root->d < n2)
        return LCA(root->r, n1, n2);
    return root;
}

int main() {
    n* root = newnode(9);
    root->l = newnode(7);
    root->r = newnode(10);
    root->l->l = newnode(6);
    root->r->l = newnode(8);
    root->r->r = newnode(19);
    root->r->l->r = newnode(4);
    root->r->r->r = newnode(20);
    
    int n1 = 20, n2 = 4;
    struct n* t = LCA(root, n1, n2);
    cout << "20 और 4 का लोएस्ट कॉमन एंसेस्टर है: " << t->d << endl;
    
    n1 = 7, n2 = 6;
    t = LCA(root, n1, n2);
    cout << "7 और 6 का लोएस्ट कॉमन एंसेस्टर है: " << t->d << endl;
}

आउटपुट

20 और 4 का लोएस्ट कॉमन एंसेस्टर है: 9
7 और 6 का लोएस्ट कॉमन एंसेस्टर है: 7

ट्री संरचना

        9
       /  \
      7    10
     /    /  \
    6    8    19
         \     \
          4     20

महत्वपूर्ण नोट

यह एल्गोरिदम बाइनरी सर्च ट्री (BST) के लिए काम करता है जहां लेफ्ट सबट्री < रूट < राइट सबट्री होता है। सामान्य बाइनरी ट्री के लिए अलग एल्गोरिदम चाहिए।

सामान्य बाइनरी ट्री के लिए LCA

Node* LCA_BT(Node* root, int n1, int n2) {
    if (!root) return NULL;
    if (root->data == n1 || root->data == n2) return root;
    
    Node* left = LCA_BT(root->left, n1, n2);
    Node* right = LCA_BT(root->right, n1, n2);
    
    if (left && right) return root;
    return left ? left : right;
}