Balanced Binary Tree

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
13 upvotes
Asked in companies
DunzoJosh Technology GroupHashedIn

Problem statement

You are given an integer 'H'. Your task is to count and print the maximum number of balanced binary trees possible with height 'H'.

The balanced binary tree is one in which, for every node, the difference between the left and right subtree heights is less than or equal to 1.

You have to print the answer with modulo 1e9+7.

For Example: 
Input:
H = 2

Output: 
3

There will be a total 3 different balanced binary trees with height 2. 
One node as a root and other nodes on one of the two sides.
One with root and left subtree with one more node than right.
One with root and right subtree with one more node than left.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.

Each test case contains a single integer 'H' denoting the height of the tree.
Output Format: 
For each test case, print an integer denoting the number of balanced binary trees that can be made with a given height. 

Answers for each test case will be printed in a separate line.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints: 
1 <= T <= 50
1 <= H <= 10^6

Time Limit: 1 sec.
Sample Input 1:
2
3
1
Sample Output 1:
15
1
Explanation For Sample Output 1:
In test case 1:
We can make 15 different balanced binary trees with a height 3.

In test case 2:
We can make only 1 balanced binary tree with a height 1.
Sample Input 1:
2
2
4
Sample Output 1:
3
315
Hint

Height of the binary tree is 1 + max(left_subtree_height, right_subtree_height).

Approaches (2)
Recursion.

As given in the problem, the difference between the heights of the left subtree and right subtree is less than or equal to one, so the heights of the left and the right part will be one of the following: 

  • (H-1), (H-2)
  • (H-2), (H-1)
  • (H-1), (H-1)

 

Hence, we can write the below relation on this. 

Say, CTR(H) be the no of ways to make a balanced binary tree of height 'H'.

So, by combinatorics, we can write. 

CTR(H) = CTR(H-1) * CTR(H-2) + 

                CTR(H-2) * CTR(H-1) + 

                CTR(H-1) * CTR(H-1)

             = 2 * CTR(H-1) * CTR(H-2) +  

               CTR(H-1) * CTR(H-1)

             = CTR(H-1) * (2*CTR(H - 2) + 

                CTR(H - 1))

Here, we can see this problem has optimal substructure properties; hence we can use simple recursion to calculate the above equation. 

 

Algorithm

  • Make a recursive function get()
  • get(h) will give the no of ways to make a balanced binary tree of height h.
  • inside get function to write the base case of recursion when h is zero or 1 return answer as 1.
  • if h is not 0 or 1 then return the get(h-1)*(2*get(h-2)+get(h-1)).
  • call get() function for given input height and return the result modulo 1e9+7.
Time Complexity

O(3^H), Where H is the height of the tree. 

 

As we are recursively calling for each sub-structure and there are three different structures, it will lead to exponential complexity.

Space Complexity

O(H), Where H is the height of the tree. 

 

As we are going till the depth of the recursive tree stack will have max storage of H nodes in this case. Hence space complexity will be O(H).

Code Solution
(100% EXP penalty)
Balanced Binary Tree
Full screen
Console