আমাদের একটি বাইনারি ট্রি দেওয়া আছে। কাজ হল বাইনারি ট্রি-এ হাফ নোড (Half Nodes) - অর্থাৎ যেসব নোডের শুধু একটি চাইল্ড আছে (অন্যটি null) - তাদের সংখ্যা ইটেরেটিভ এবং রিকারসিভ পদ্ধতিতে গণনা করা। লিফ নোড (leaf nodes) হাফ নোড नहीं।
উদাহরণ:
ইনপুট: (ট্রি চিত্র)
আউটপুট: count is 2
ব্যাখ্যা: ট্রিতে ২টি নোড (৪০ এবং ৫০) আছে যাদের ঠিক একটি চাইল্ড রয়েছে।
ইটেরেটিভ পদ্ধতি
লেভেল অর্ডার ট্রাভার্সাল (BFS) ব্যবহার করে কিউ দিয়ে প্রতিটি নোড চেক করুন। যদি (left null AND right != null) OR (left != null AND right null) হয় তবে কাউন্ট বাড়ান।
প্রোগ্রাম (ইটেরেটিভ)
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
int halfcount(struct Node* node) {
if (!node) return 0;
int result = 0;
queue myqueue;
myqueue.push(node);
while (!myqueue.empty()) {
struct Node* temp = myqueue.front();
myqueue.pop();
if ((!temp->left && temp->right) || (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: " << halfcount(root);
return 0;
}
আউটপুট
count is: 2
রিকারসিভ পদ্ধতি
রিকারসিভ ফাংশনে: যদি নোড null হয় তবে ০ রিটার্ন। যদি ঠিক একটি চাইল্ড থাকে তবে ১ যোগ করে left ও right সাবট্রির ফলাফল যোগ করুন।
প্রোগ্রাম (রিকারসিভ)
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
int halfcount(struct Node* root) {
if (root == NULL) return 0;
int result = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL))
result++;
result += halfcount(root->left) + halfcount(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: " << halfcount(root);
return 0;
}
আউটপুট
count is: 2
