একটি বাইনারি ট্রির উচ্চতা H দেওয়া আছে। সেই উচ্চতার সমতুল্য (height-balanced) বাইনারি ট্রি কতটি সম্ভব সেটি বের করতে হবে। সমতুল্য বাইনারি ট্রি মানে প্রতিটি নোডের বাম ও ডান সাবট্রির উচ্চতার পার্থক্য হয় ০ বা ১।
উদাহরণ
Height H = 2 → Count = 3 Height H = 3 → Count = 15 Height H = 4 → Count = 315
রিকারসিভ সূত্র
উচ্চতা h-এর সমতুল্য ট্রির সংখ্যা:
count(h) = count(h-1) * (2 * count(h-2) + count(h-1))
বেস কেস: h = 0 বা 1 হলে count = 1।
C++ প্রোগ্রাম
#include <iostream>
using namespace std;
int countBTheight(int h) {
if (h == 0 || h == 1) return 1;
return countBTheight(h-1) * (2 * countBTheight(h-2) + countBTheight(h-1));
}
int main() {
int H = 4;
cout << "Count of balanced binary trees of height H is: " << countBTheight(H);
return 0;
}
আউটপুট: Count of balanced binary trees of height H is: 315
দ্রষ্টব্য: বড় h-এর জন্য এই রিকারসিভ পদ্ধতি ধীর। ডাইনামিক প্রোগ্রামিং বা মেমোইজেশন দিয়ে অপ্টিমাইজ করা যায়।
