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