Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Balanced Binary Tree

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
10 upvotes
Asked in companies
DunzoFlipkartHashedIn

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 )
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
Full screen
Console