Balanced Binary Tree
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

Question

Balanced Binary Tree

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.

Accepted Answer

The maximum number of balanced binary trees possible with a given height is to be counted and printed.

A balanced binary tree is one in which the difference between the left and right subtree heights is less than or equal to 1.
The number of balanced binary trees can be calculated using dynamic programming.
The number of balanced binary trees with height 'H' can be obtained by summing the product of the number of balanced binary trees for each possible left and right subtree heights.
Use modulo 1e9+7 to handle large numbers and print the result.

Accepted Answer

I used postorder tee traversal to solve this problem, first go on left subtree and return the height, similarly gets height of right subtree and check if absolute difference is less than or equal to 1.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

Time Complexity: OtherExplanation:

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.

Accepted Answer

Dynamic Programming.

From the recursive approach, we are calculating the below equation.

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

In the above equation, as we can see, we are calculating some values again and again like we are calling CTR(H-1) two times there and the same with all values. Using dynamic programming, we can pre calculate all values, which can be used to generate the above equation effectively.

Algorithm

Initialize the dp array of size h+1
Initialize mod as 1e9+7 we will use this to avoid overflow and return the answer after taking modulo with it.
Make dp[0] and dp[1] equal to 1. this are base cases
Run a loop from 2 to h+1 and update each of the dp states.
Make dp[i] = (dp[i-1] * (2* dp[i-2]%mod + dp[i-1]%mod)%mod.
Return the dp[h].

Space Complexity: OtherExplanation:

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

Because we are using a DP array of size H to store the DP states.

Time Complexity: OtherExplanation:

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

As we are traversing the DP array of size H, the complexity will be O(H).

Python (3.5)

'''



    Time Complexity: O(h)

    Space Complexity: O(h)



    Where, 'h' is the height of the tree.



'''



def balencedBTree(h):

    

    # Initialising variable mod.

    mod = int(1e9 + 7)

    

    # Initialising DP array.

    dp = [0 for i in range(h + 1)]

    

    # Base cases.

    dp[0] = 1

    dp[1] = 1

    

    # Updating the dp array.

    for i in range(2, h + 1):

        

        dp[i] = (dp[i - 1] * ((2 * dp[i - 2]) % mod + dp[i - 1]) % mod) % mod

        

    # Returning the dp[h].

    return dp[h]

Java (SE 1.8)

/*



    Time Complexity: O(h)

    Space Complexity: O(h)



    Where, 'h' is the height of the tree.



*/



public class Solution {

    public static int balencedBTree(int h){



        // Initialising variable mod.

        int mod =(int) 1e9 + 7;



        // Initialising DP array.

        long []dp=new long[h + 1];



        // Base cases.

        dp[0] = dp[1] = 1;



        // Updating the dp array.

        for (int i = 2; i <= h; i++) {

            dp[i] = (dp[i - 1] * ((2 * dp[i - 2]) % mod + dp[i - 1]) % mod) % mod;

        }



        // Returning the dp[h].

        return (int)dp[h];

    }

}

C++ (g++ 5.4)

/*



    Time Complexity: O(h)

    Space Complexity: O(h)



    Where, 'h' is the height of the tree.



*/



int balencedBTree(int h) {



    // Initialising variable mod.

    int mod = 1e9 + 7;



    // Initialising DP array.

    long long dp[h + 1];



    // Base cases.

    dp[0] = dp[1] = 1;



    // Updating the dp array.

    for (int i = 2; i <= h; i++) {

        dp[i] = (dp[i - 1] * ((2 * dp[i - 2]) % mod + dp[i - 1]) % mod) % mod;

    }



    // Returning the dp[h].

    return (int)dp[h];

}

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 Format:

Output Format:

Note:

Constraints:

Top Josh Technology Group Software Developer interview questions & answers

Popular interview questions of Software Developer