এই টিউটোরিয়ালে, আমরা বাইনারি গাছের গভীরতম বাম পাতার নোড খুঁজে বের করতে যাচ্ছি। চলুন বাইনারি ট্রি দেখি।
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
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
