এই টিউটোরিয়ালে আমরা বাইনারি ট্রিতে গভীরতম বাম লিফ নোড (deepest left leaf node) খুঁজে বের করব। নিচে একটি বাইনারি ট্রির উদাহরণ দেওয়া হলো:
A
/ \
B C
/ / \
D E F
\
G
সমস্যা সমাধানের ধাপসমূহ
ক্যरेক্টার (char), লেফট (left) এবং রাইট (right) পয়েন্টার সহ একটি নোড স্ট্রাকচার (struct) লিখুন।
ডামি ডেটা দিয়ে বাইনারি ট্রিটি ইনিশিয়ালাইজ করুন।
বাইনারি ট্রিতে গভীরতম বাম নোড খুঁজে বের করার জন্য একটি রিকারসিভ ফাংশন লিখুন। এটি তিনটি আর্গুমেন্ট নেয়: রুট নোড, isLeftNode, এবং রেজাল্ট পয়েন্টার (গভীরতম নোড সংরক্ষণের জন্য)।
যদি বর্তমান নোড বাম পাশে থাকে এবং লিফ নোড হয়, তবে রেজাল্ট নোডকে বর্তমান নোড দিয়ে আপডেট করুন।
বাম সাব-ট্রিতে রিকারসিভ ফাংশনটি কল করুন।
ডান সাব-ট্রিতে রিকারসিভ ফাংশনটি কল করুন।
যদি রেজাল্ট নোড নাল (null) হয়, তবে আমাদের শর্ত পূরণকারী কোনো নোড নেই।
অন্যথায় রেজাল্ট নোডের ডেটা প্রিন্ট করুন।
উদাহরণ
নিচে কোডটি দেওয়া হলো:
#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
নিষ্কর্ষ
এই টিউটোরিয়াল সম্পর্কে আপনার কোনো প্রশ্ন থাকলে কমেন্ট সেকশনে জানাতে পারেন।
