C++ में बाइनरी ट्री में सबसे गहरा बायां पत्ता नोड ढूंढना

परिचय

इस ट्यूटोरियल में हम बाइनरी ट्री में सबसे गहरे (deepest) बाएं पत्ते (left leaf) नोड को ढूंढना सीखेंगे। एक बाइनरी ट्री में, पत्ता नोड वह होता है जिसके कोई बच्चे नहीं होते, और बायां पत्ता वह होता है जो अपने पैरेंट का बायां बच्चा होता है।

बाइनरी ट्री उदाहरण

    A
   / \
  B   C
 /   / \
D   E   F
     \
      G

समस्या समाधान के चरण

1. कैरेक्टर डेटा, लेफ्ट और राइट पॉइंटर्स के साथ एक नोड स्ट्रक्चर लिखें।
2. डमी डेटा के साथ बाइनरी ट्री को इनिशियलाइज़ करें।
3. बाइनरी ट्री में सबसे गहरे बाएं नोड को ढूंढने के लिए एक रिकर्सिव फंक्शन लिखें। यह तीन आर्गुमेंट्स लेता है: रूट नोड, isLeftNode फ्लैग, और रिजल्ट पॉइंटर सबसे गहरे नोड को स्टोर करने के लिए।
4. यदि वर्तमान नोड बायां है और पत्ता नोड है, तो रिजल्ट नोड को वर्तमान नोड से अपडेट करें।
5. बाएं सबट्री पर रिकर्सिव फंक्शन कॉल करें।
6. दाएं सबट्री पर रिकर्सिव फंक्शन कॉल करें।
7. यदि रिजल्ट नोड नल है, तो कोई ऐसा नोड नहीं है जो हमारी शर्तों को पूरा करता हो।
8. अन्यथा रिजल्ट नोड में डेटा प्रिंट करें।

उदाहरण कोड

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char data;
    struct Node *left, *right;
};

Node *addNewNode(char data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void getDeepestLeftLeafNode(Node *root, bool isLeftNode, Node **resultPointer) {
    if (root == NULL) return;
    if (isLeftNode && !root->left && !root->right) {
        *resultPointer = root;
        return;
    }
    getDeepestLeftLeafNode(root->left, true, resultPointer);
    getDeepestLeftLeafNode(root->right, false, resultPointer);
}

int main() {
    Node* root = addNewNode('A');
    root->left = addNewNode('B');
    root->right = addNewNode('C');
    root->left->left = addNewNode('D');
    root->right->left = addNewNode('E');
    root->right->right = addNewNode('F');
    root->right->left->right = addNewNode('G');
    Node *result = NULL;
    getDeepestLeftLeafNode(root, false, &result);
    if (result) {
        cout << "The deepest left child is " << result->data << endl;
    } else {
        cout << "There is no left leaf in the given tree" << endl;
    }
    return 0;
}

आउटपुट

The deepest left child is D

निष्कर्ष

इस प्रोग्राम में हमने बाइनरी ट्री में सबसे गहरे बाएं पत्ते नोड (D) को सफलतापूर्वक ढूंढ लिया। रिकर्सिव दृष्टिकोण ट्री को गहराई-पहले तरीके से ट्रैवर्स करता है और हर बार बाएं पत्ते मिलने पर रिजल्ट को अपडेट करता है, जिससे अंत में सबसे गहरा बायां पत्ता मिलता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।