> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/count-balanced-binary-trees-of-height-h.md).

# Count Balanced Binary Trees of Height h

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
```

### [Recommended: Please solve it on “**PRACTICE**” first, before moving on to the solution.](https://practice.geeksforgeeks.org/problems/bbt-counter/0)

Following are the balanced binary trees of height 3.<br>

![](https://media.geeksforgeeks.org/wp-content/uploads/TreeNodes-1.png)

Height of tree, h = 1 + max(left height, right height)\
Since the difference between the heights of left and right subtree is not more than one, possible heights of left and right part can be one of the following:

1. (h-1), (h-2)
2. (h-2), (h-1)
3. (h-1), (h-1)

```
count(h) = count(h-1) * count(h-2) + 
           count(h-2) * count(h-1) + 
           count(h-1) * count(h-1)
        = 2 * count(h-1) * count(h-2) +  
          count(h-1) * count(h-1)
       = count(h-1) * (2*count(h - 2) + 
                          count(h - 1))
```

```java
class Solution {
    static int MOD = 1000000007;

    public static long countBT(int h) {
        long[] dp = new long[h + 1];
        // dp[i] -> number of balanced BT of height i
        // base cases
        dp[0] = 1;
        dp[1] = 1;
        // dp[i] -> dp[i-1]*dp[i-1] OR dp[i-1]*dp[i-2] OR dp[i-2]*dp[i-1]
        for (int i = 2; i <= h; ++i)
            dp[i] = (dp[i - 1] * ((2 * dp[i - 2]) % MOD + dp[i - 1]) % MOD) % MOD;

        return dp[h];
    }
}
```