আমাদের একটি বাইনারি ট্রি দেওয়া আছে। কাজ হল বাইনারি ট্রি-এ ফুল নোড (Full Nodes) - অর্থাৎ যেসব নোডের দুটি চাইল্ড (left এবং right) আছে এবং কোনোটিই null নয় - তাদের সংখ্যা ইটেরেটিভ (Iterative) এবং রিকারসিভ (Recursive) পদ্ধতিতে গণনা করা।
বাইনারি ট্রি হল একটি বিশেষ ডেটা স্ট্রাকচার। প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে।
উদাহরণ:
ইনপুট: (ট্রি চিত্র)
আউটপুট: count is 2
ব্যাখ্যা: ট্রিতে ২টি নোড (১০ এবং ২০) আছে যাদের দুটি চাইল্ড রয়েছে।
ইটেরেটিভ পদ্ধতি
লেভেল অর্ডার ট্রাভার্সাল (BFS) ব্যবহার করে কিউ (queue) দিয়ে প্রতিটি নোড ভিজিট করুন। যদি নোডের left এবং right দুটোই null না হয়, তবে কাউন্ট বাড়ান।
প্রোগ্রাম (ইটেরেটিভ)
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
// ফুল নোড গণনা (ইটেরেটিভ)
int fullcount(struct Node* node) {
if (!node) return 0;
queue myqueue;
int result = 0;
myqueue.push(node);
while (!myqueue.empty()) {
struct Node* temp = myqueue.front();
myqueue.pop();
if (temp->left && temp->right) result++;
if (temp->left != NULL) myqueue.push(temp->left);
if (temp->right != NULL) myqueue.push(temp->right);
}
return result;
}
struct Node* newNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int main() {
struct Node* root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout << "count is: " << fullcount(root);
return 0;
}
আউটপুট
count is: 2
রিকারসিভ পদ্ধতি
রিকারসিভ ফাংশনে: যদি নোড null হয় তবে ০ রিটার্ন। যদি left এবং right দুটোই থাকে তবে ১ যোগ করে left ও right সাবট্রির ফলাফল যোগ করুন।
প্রোগ্রাম (রিকারসিভ)
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
int fullcount(struct Node* root) {
if (root == NULL) return 0;
int result = 0;
if (root->left && root->right) result++;
result += fullcount(root->left) + fullcount(root->right);
return result;
}
struct Node* newNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int main() {
struct Node* root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout << "count is: " << fullcount(root);
return 0;
}
আউটপুট
count is: 2
