ফুল বাইনারি ট্রি হলো যেখানে প্রতিটি নোডের ০ বা ২টি চাইল্ড থাকে (১টি চাইল্ড থাকে না)। রিকার্সিভলি চেক করা যায়।
অ্যালগরিদম
- বেস কেস: NULL রুট → true
- লিফ নোড (দুই চাইল্ড NULL) → true
- দুই চাইল্ড আছে → বাম ও ডান সাবট্রি রিকার্সিভ চেক
- অন্যথায় (১টি চাইল্ড) → false
উদাহরণ কোড
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(int d) : data(d), left(nullptr), right(nullptr) {}
};
bool isFullBinaryTree(TreeNode* root) {
if (!root) return true;
if (!root->left && !root->right) return true;
if (root->left && root->right)
return isFullBinaryTree(root->left) && isFullBinaryTree(root->right);
return false;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
// root->right->right = NULL; // এখানে ১টি চাইল্ড, তাই Full Binary Tree নয়
cout << (isFullBinaryTree(root) ? 1 : 0) << endl;
return 0;
}
আউটপুট
0
রাইট চাইল্ডের রাইট চাইল্ড নেই, তাই ফুল বাইনারি ট্রি নয়।
