একটি সম্পূর্ণ বাইনারি ট্রি (Complete Binary Tree) দেওয়া আছে। ট্রির মোট নোড সংখ্যা দক্ষতার সাথে গণনা করতে হবে।
অ্যালগরিদম (রিকার্সিভ)
- বাম সাবট্রির উঁচু (hl) এবং ডান সাবট্রির উঁচু (hr) বের করুন
- যদি hl == hr হয়, তবে ট্রিটি পারফেক্ট বাইনারি ট্রি, নোড সংখ্যা = 2^hl - 1
- অন্যথায়: 1 + countNodes(left) + countNodes(right)
সময় জটিলতা: O(log²n)
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) { val = data; left = right = NULL; }
};
void insert(TreeNode **root, int val) {
queue<TreeNode*> q;
q.push(*root);
while (q.size()) {
TreeNode *temp = q.front(); q.pop();
if (!temp->left) {
if (val != NULL) temp->left = new TreeNode(val);
else temp->left = new TreeNode(0);
return;
} else q.push(temp->left);
if (!temp->right) {
if (val != NULL) temp->right = new TreeNode(val);
else temp->right = new TreeNode(0);
return;
} else q.push(temp->right);
}
}
TreeNode* make_tree(vector<int> v) {
TreeNode *root = new TreeNode(v[0]);
for (int i = 1; i < v.size(); i++) insert(&root, v[i]);
return root;
}
class Solution {
public:
int fastPow(int base, int power) {
int res = 1;
while (power > 0) {
if (power & 1) res *= base;
base *= base;
power >>= 1;
}
return res;
}
int countNodes(TreeNode* root) {
int hr = 0, hl = 0;
TreeNode* l = root;
TreeNode* r = root;
while (l) { hl++; l = l->left; }
while (r) { r = r->right; hr++; }
if (hl == hr) return fastPow(2, hl) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
int main() {
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8,9,10};
TreeNode *node = make_tree(v);
cout << ob.countNodes(node);
return 0;
}
ইনপুট / আউটপুট
Input: [1,2,3,4,5,6,7,8,9,10] Output: 10
