इस ट्यूटोरियल में, हम बाइनरी ट्री में सबसे गहरे लेफ्ट लीफ नोड को खोजने जा रहे हैं। आइए देखते हैं बाइनरी ट्री।
A B C D E F G
आइए समस्या को हल करने के लिए चरणों को देखें।
-
चार, बाएँ और दाएँ पॉइंटर्स के साथ एक नोड संरचना लिखें।
-
डमी डेटा के साथ बाइनरी ट्री को इनिशियलाइज़ करें।
-
बाइनरी फ़ंक्शन में सबसे गहरे बाएं नोड को खोजने के लिए एक पुनरावर्ती फ़ंक्शन लिखें। गहरे नोड को स्टोर करने के लिए तीन तर्क रूट नोड, isLeftNode, और परिणाम सूचक लेता है।
-
यदि वर्तमान नोड बचा है और लीफ नोड है, तो परिणाम नोड को वर्तमान नोड से अपडेट करें।
-
बाएं उप-वृक्ष पर पुनरावर्ती फ़ंक्शन को कॉल करें।
-
रिकर्सिव फंक्शन को राइट सब ट्री पर कॉल करें।
-
यदि परिणाम नोड शून्य है, तो ऐसा कोई नोड नहीं है जो हमारी शर्तों को पूरा करता हो।
-
अन्यथा परिणाम नोड में डेटा प्रिंट करें।
उदाहरण
आइए कोड देखें।
#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
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उनका टिप्पणी अनुभाग में उल्लेख करें।