এই টিউটোরিয়ালে, আমরা শিখতে যাচ্ছি কিভাবে একটি বাইনারি ট্রিতে গভীরতম বিজোড় স্তরের নোড খুঁজে বের করতে হয়।
এটি বাইনারি গাছের গভীরতা খোঁজার মতো। এখানে, আমাদের আরও একটি শর্ত রাখতে হবে যেমন, বর্তমান স্তরটি বিজোড় কিনা।
আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷-
ডামি ডেটা দিয়ে বাইনারি ট্রি শুরু করুন।
-
একটি বাইনারি ট্রিতে গভীরতম বিজোড় স্তরের নোড খুঁজে পেতে একটি পুনরাবৃত্ত ফাংশন লিখুন৷
-
যদি বর্তমান নোডটি একটি লিফ নোড হয় এবং স্তরটি বিজোড় হয়, তাহলে বর্তমান স্তরটি ফেরত দিন৷
-
অন্যথায় রিকার্সিভ ফাংশন কল সহ বাম নোড এবং ডান নোডের সর্বাধিক ফেরত দিন।
-
-
গভীরতম বিজোড় স্তরের নোড প্রিন্ট করুন৷
৷
উদাহরণ
আসুন কোডটি দেখি।
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int oddLeafDepthInTree(struct Node *root, int level) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL && level % 2 == 1) {
return level;
}
return max(oddLeafDepthInTree(root->left, level + 1), oddLeafDepthInTree(root->right, level + 1));
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(6);
root->right->left->right = newNode(7);
root->right->right->right = newNode(8);
int level = 1, depth = 0;
cout << oddLeafDepthInTree(root, level) << endl;
return 0;
} আউটপুট
আপনি যদি উপরের কোডটি কার্যকর করেন, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
3
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
