Problem of the day
You are given an integer ‘N’, you are supposed to find the number of balanced binary trees with height ‘N’. Since the answer can be very large, return the answer modulo 10^9+7.
Note :A binary tree is considered balanced if the difference between the left subtree’s height and the right subtree’s height is less than or equal to 1, for all non-leaf nodes.
Example:
Consider N=2, there are three different binary trees.
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains a single integer ‘N’ denoting the height of the balanced binary tree.
Output Format :
For each test case, print the number of balanced binary trees with height ‘N’ modulo 10^9+7.
Print the output of each test case on a new line.
Note :
You don’t need to print anything; It has already been taken care of.
1 <= T <= 50
1 <= N <= 10 ^ 4
Where ‘T’ denotes the number of test cases, ‘N’ denotes the height of the balanced binary tree.
Time Limit: 1 sec
2
2
3
3
15
In the first test case, the total number of binary trees with height 2 is 3.
In the second test case, the total number of binary trees with height 3 is 15.
1
4
315
The total number of binary trees with height 4 is 315.
Can you think about different possible combinations of heights of left and right subtree for any node?
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:
The steps are as follows:
O(2^N), where ‘N’ is the height of the balanced binary tree.
Since at any height, we have always two options possible that either we can create a left subtree of one less height than the current root and a right subtree of two less height than the current root and vice - versa and for each possibility, we will make 2 recursive function calls. Thus for ‘N’ height, total possibilities will be 2^N, so there will be a total of 2^N function calls. Thus, the overall time complexity is O( 2^N ).
O(N), where N is the height of the balanced binary tree.
We are using recursion to count to the number of balanced binary trees with height N. The recursion stack grows maximum up to a size of ‘N’ because in each instance of recursion our height must be decreased by one or two. Thus, the overall space complexity is O(N).