New update is available. Click here to update.

Balanced Binary Tree

Posted: 1 Jul, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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