Number of balanced binary trees

Easy
0/40
Average time to solve is 10m
18 upvotes
Asked in companies
ZomatoJosh Technology GroupBlackrock

Problem statement

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.

Example

Detailed explanation ( Input/output format, Notes, Images )
Input Format :
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.
Constraints :
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
Sample Input 1 :
2
2
3
Sample Output 1 :
3
15
Explanation of Sample Input 1 :
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.
Sample Input 2 :
1
4
Sample Output 2 :
315
Explanation of Sample Input 2 :
The total number of binary trees with height 4 is 315.
Hint

Can you think about different possible combinations of heights of left and right subtree for any node?

Approaches (4)
Recursive brute force

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.
Time Complexity

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 ).

Space Complexity

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).

Code Solution
(100% EXP penalty)
Number of balanced binary trees
Full screen
Console