Number of balanced binary trees

For solving the problem, let us first fix the root node at level 1. Since we have fixed the root node we have N-1 levels left, now we have to count the number of ways we can create a balanced binary tree of height (N-1) at the left and the right subtree of the root node; hence we have reduced the problem from finding the number of balanced binary trees with height ‘N’ to finding the number of balanced binary trees with height ‘N-1’. This substructure property paves the way for a recursive solution.

For finding the number of balanced binary trees with height ‘N’, we will fix the root node, and then we will have the following possibilities:

1. The left subtree has a height (N-1), and the right subtree has a height (N-2).
2. The left subtree has a height (N-2), and the right subtree has a height (N-1).
3. Both the left subtree and the right subtree have a height (N-1).

The steps are as follows:

1. Let’s define a function countTree(height) which will return the number of balanced binary trees of height “height”.
2. The base case for this function will be when ‘height’ is either 0 or 1. We will have one balanced binary tree in both cases. In the case of 0, the tree will be NULL without any nodes, and for height=1, it will be a single root node.
3. Otherwise, we will recur for the left and right subtree with height “height-1” and cover the three possibilities mentioned above.
   1. countTree(height-1) * countTree(height-2) {Multiplication because of independent events, i.e. our left combination doesn’t affect the right combination.}
   2. countTree(height-2) * countTree(height-1) {Multiplication because of independent events, i.e. our left combination doesn’t affect the right combination.}
   3. countTree(height-1) * countTree(height-1) {Multiplication because of independent events, i.e. our left combination doesn’t affect the right combination.}
4. The final answer will be the sum of the three values(Sum because of dependent events. I.e. at a time only one event can occur out of three) returned by the recursive function calls modulo 10^9+7.

The idea is to use dynamic programming to store the result of a subproblem so that instead of solving the same problem more than once, we can use the stored result.

The steps are as follows:

1. Let’s declare an array “dp” to store the results of the subproblems. Let’s define dp[i] as the number of balanced binary trees with height ‘i’. Initially, all elements in the “dp” array are -1.
2. Let’s define a function countTree(height) which will return the number of balanced binary trees of height ‘height’.
3. The base case for this function will be when ‘height’ is either 0 or 1. We will have one balanced binary tree in both cases. In the case of 0, the tree will be NULL without any nodes, and for height=1, it will be a single root node.
4. Otherwise, we will recur for the left and right subtree with height “height-1” and cover the three possibilities mentioned above.
   1. countTree(height-1) * countTree(height-2) {Multiplication because of independent events, i.e. our left combination doesn’t affect the right combination.}
   2. countTree(height-2) * countTree(height-1) {Multiplication because of independent events, i.e. our left combination doesn’t affect the right combination.}
   3. countTree(height-1) * countTree(height-1) {Multiplication because of independent events, i.e. our left combination doesn’t affect the right combination.}
5. Store the sum of the three values(Sum because of dependent events. I.e. at a time only one event can occur out of three)  returned by the recursive function calls modulo 10^9+7 in dp[height]
6. Return the value of dp[height].

The idea is to use dynamic programming to store the results of a subproblem and then use the stored results to solve other subproblems.

We will iterate from 1 to ‘N’ and compute and store the result in an array. We will then use the stored results to compute the final answer.

The steps are as follows :

1. Let’s declare an array “dp” to store the results of the subproblems. Let’s define dp[i] as the number of balanced binary trees with height ‘i’. Initially, dp[0] and dp[1] are equal to 1.
2. Iterate from 2 to ‘N’, let’s say the current index is ‘i’.
3. The value of dp[i] can be calculated by considering the three possibilities.
   1. The left subtree has a height (i-1), and the right subtree has a height (i-2). This value is given by dp[i-1]*dp[i-2].
   2. The left subtree has a height (i-2), and the right subtree has a height (i-1). This value is given by dp[i-2]*dp[i-1].
   3. Both the left subtree and the right subtree have a height (i-1). This value is given by dp[i-1]*dp[i-1].
   4. The value of dp[i] will be equal to the sum of the above three values modulo 10^9+7.
4. The value of dp[N] will be equal to the total number of balanced binary trees with height ‘N’, hence we will return dp[N].

In the previous approach, for calculating the number of balanced binary trees with height “height” we only needed the values of the number of balanced binary trees with height “height-1” and the number of balanced binary trees with height “height-2”. Hence it will be sufficient to store the results of only the previous 2 subproblems. This way we will be able to solve this problem in constant space.

We will iterate from 2 to ‘N’ and compute and store the result of the last 2 iterations in two variables. We will then use the stored results to compute the final answer.

The steps are as follows:

1. Let’s define a variable “prevOne” to store the result of the previous subproblem and another variable “prevTwo” to store the result of the 2nd last subproblem. Suppose currently we want to compute the result for height =”height” then prevOne will be storing the result for height “height-1” and prevTwo will be storing the result for height “height-2”  Initially, prevOne and prevTwo will store the result for height 0 and 1 respectively. Hence, both of them will be initialized to 1.
2. Iterate from 2 to ‘N’, let’s say the current index is ‘i’.
3. The number of balanced binary trees with height ‘i’ can be calculated by considering the three possibilities.
   1. The left subtree has a height (i-1), and the right subtree has a height (i-2). This value is given by prevOne * prevTwo.
   2. The left subtree has a height (i-2), and the right subtree has a height (i-1). This value is given by prevTwo * prevOne.
   3. Both the left subtree and the right subtree have a height (i-1). This value is given by prevOne * prevOne.
   4. The number of balanced binary trees with height will be equal to the sum of the above three values modulo 10^9+7.
   5. Store the sum of the above possibilities in a variable called “currentHeight”.
   6. Change the value of “prevTwo” to “prevOne” and change the value of “prevOne” to “currentHeight”.
4. The value of prevOne will be equal to the number of balanced binary trees of height ‘N’, hence we will return “prevOne”.