C++ प्रोग्राम: बाइनरी ट्री में सबसे गहरा लेफ्ट लीफ ढूंढना

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

एल्गोरिदम

शुरुआत
    deepestLLeafutil() फ़ंक्शन दिए गए बाइनरी ट्री में सबसे गहरा लेफ्ट लीफ ढूंढता है:
        lvel वर्तमान नोड का लेवल है
        maxlvel अब तक मिले सबसे गहरे लेफ्ट लीफ नोड का पॉइंटर है
        isLeft इंगित करता है कि यह नोड अपने पैरेंट का लेफ्ट चाइल्ड है
        resPtr रिजल्ट का पॉइंटर है
        यदि रूट NULL के बराबर है तो
            लौटें
        रिजल्ट अपडेट करें यदि यह नोड लेफ्ट लीफ है और इसका लेवल वर्तमान रिजल्ट के मैक्स लेवल से अधिक है
        लेफ्ट और राइट सबट्रीज के लिए deepestLLeafutil() फ़ंक्शन को रिकर्सिवली कॉल करें
समाप्ति

उदाहरण कोड

#include <iostream>
using namespace std;

struct n {
    int v;
    n *l, *r;
};

void deepestLLeafutil(n* root, int lvel, int* maxvel, bool isLeft, n** resPtr) {
    if (root == NULL)
        return;
    if (isLeft && !root->l && !root->r && lvel > *maxvel) {
        *resPtr = root;
        *maxvel = lvel;
        return;
    }
    deepestLLeafutil(root->l, lvel + 1, maxvel, true, resPtr);
    deepestLLeafutil(root->r, lvel + 1, maxvel, false, resPtr);
}

n* deepestLLeaf(n* root) {
    int maxlevel = 0;
    n* res = NULL;
    deepestLLeafutil(root, 0, &maxlevel, false, &res);
    return res;
}

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

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);
    
    n* res = deepestLLeaf(root);
    if (res)
        cout << "सबसे गहरा लेफ्ट लीफ है " << res->v;
    else
        cout << "दिए गए ट्री में कोई लेफ्ट लीफ नहीं है";
    return 0;
}

आउटपुट

सबसे गहरा लेफ्ट लीफ है 6

ट्री संरचना

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

लेफ्ट लीफ्स: 6 (लेवल 2), 4 (लेवल 3) - लेकिन 4 राइट चाइल्ड है 8 का, इसलिए लेफ्ट लीफ नहीं। केवल 6 लेफ्ट लीफ है।

एल्गोरिदम व्याख्या

• isLeft पैरामीटर ट्रैक करता है कि नोड अपने पैरेंट का लेफ्ट चाइल्ड है या नहीं
• लीफ चेक: !root->l && !root->r - दोनों चाइल्ड NULL हैं
• लेवल ट्रैकिंग: प्रत्येक रिकर्सिव कॉल पर लेवल बढ़ता है
• मैक्स लेवल अपडेट: केवल तब जब नया लेफ्ट लीफ गहरा मिले

समय जटिलता

• O(n) - प्रत्येक नोड एक बार विजिट होता है
• स्पेस: O(h) - रिकर्सन स्टैक, h = ट्री की ऊंचाई