Number of Binary Search Trees of height H consisting of H+1 nodes

Number of Binary Search Trees of height H consisting of H+1 nodes

Given a positive integer H, the task is to find the number of possible Binary Search Trees of height H consisting of the first (H + 1) natural numbers as the node values. Since the count can be very large, print it to modulo 10⁹ + 7.

Examples:

Input: H = 2
Output: 4
Explanation: All possible BSTs of height 2 consisting of 3 nodes are as follows:

Therefore, the total number of BSTs possible is 4.

Input: H = 6
Output: 64

Approach: The given problem can be solved based on the following observations: 

• Only (H + 1) nodes are can be used to form a Binary Tree of height H.
• Except for the root node, every node has two possibilities, i.e. either to be the left child or to be the right child. 
• Considering T(H) to be the number of BST of height H, where T(0) = 1 and T(H) = 2 * T(H – 1).
• Solving the above recurrence relation, the value of T(H) is 2^H.

Therefore, from the above observations, print the value of 2^H as the total number of BSTs of height H consisting of the first (H + 1) natural numbers.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    const int mod = 1000000007;    int power(long long x, unsigned int y) {          int res = 1;             x = x % mod;             if (x == 0)         return 0;        while (y > 0) {                              if (y & 1)             res = (res * x) % mod;                     y = y >> 1;                     x = (x * x) % mod;     }             return res; }    int CountBST(int H) {        return power(2, H); }    int main() {     int H = 2;     cout << CountBST(H);        return 0; }

Time Complexity: O(log₂H)
Auxiliary Space: O(1)

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets