Problem Statement

Given a height h, count and return the maximum number of balanced binary trees possible with height h. A balanced binary tree is one in which for every node, the difference between heights of left and right subtree is not more than 1.Examples :

Input : h = 3
Output : 15

Input : h = 4
Output : 315

Problem Link

Count Balanced Binary Trees of Height h - GeeksforGeeks

Code

DP Based Solution

#define mod 1000000007
class Solution {
  public:
    long long int countBT(int h) { 
       long long int dp[h+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for(long long int i=2;i<=h;i++)
        // dp[i] = 2*dp[i-1]*dp[i-2] + dp[i-1]*dp[i-1];
        
        dp[i] = (dp[i-1]%mod*((2*dp[i-2]+dp[i-1])%mod))%mod;
        return dp[h];
        
        
        
    }
};