1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach
3.1.
Example
3.2.
Program
4.
4.1.
What is a Binary Tree?
4.2.
What are Binary Search Trees?
4.3.
Why are Binary Search Trees used?
5.
Conclusion
Last Updated: Mar 27, 2024

# Number of Binary Search Trees of Height H Consisting of H+1 Nodes

## Introduction

Mathematics and Computing are the most dependent fields of study. One is the language of the other. With time, mathematicians have felt the need for a device that can perform calculations more quickly, which has led to the development of computers.

Form recursion to AI is somehow related to mathematics.

The problem we are going to discuss today also is a maths problem. So letâ€™s get started.

Also see, Data Structures

## Problem Statement

You are given an integer â€˜Hâ€™. You have to count the number of BSTâ€™s of height â€˜Hâ€™, which consists of the first â€˜H + 1â€™ natural numbers as nodes.

Note: Since the count of these BSTâ€™s can be pretty large, return the â€˜COUNTâ€™ modulo 10^9+7.

## Approach

Every BST with a height of â€˜Hâ€™ and containing only â€˜H+1â€™ nodes will be a skew binary search tree. And in a skew BST, at each node, we can either choose the greatest value or the smallest value from the given set of nodes.

### Example

So for each â€˜Hâ€™ node value in the BST, we choose from two values, either the greatest or the smallest, except for the last â€˜H + 1th node, where weâ€™ll have only one choice.

So the number of BSTâ€™s with height â€˜Hâ€™ and nodes value from 1 to â€˜H + 1 are 2 * 2 * . . 2 (H times) = 2 ^ H. .

Now that we know we just have to calculate 2^H, letâ€™s see how the algorithm works.

1. Initialize two integers X = 2 and COUNT = 1.
2. Next, we loop until â€˜Hâ€™ is not zero.
1. If â€˜Hâ€™ is odd, multiply â€˜Xâ€™ with â€˜COUNT.â€™
2. Next, divide â€˜Hâ€™ by two.
3. And update â€˜Xâ€™ to â€˜X * X.â€™ {Since A ^ B = (A * A) ^ (B /2), where B is even.}
3. Return â€˜COUNTâ€™.

### Program

``````#include <iostream>
using namespace std;

const int modulo = 1000000007;
typedef long long ll;

// Function counts the number of Binary Search Trees of height H consisting of H + 1 nodes.
int countNumberOfBST(int h)
{
// Initialize x=2.
ll x = 2;

// 'COUNT' that will store 2^'H'.
int count = 1;

// Loop until 'H' is not zero.
while (h > 0)
{
// If 'H' is odd, multiply 'COUNT' with 'X.â€™
if (h & 1)
{
count = (count * x) % modulo;
}

// Now divide 'H' by two.
h = h >> 1;

// Update 'X' to 'X'^2.
x = (x * x) % modulo;
}

// Return the 'COUNT'.
return count;
}

int main()
{
int h;
cout << "Enter the value of H: ";
cin >> h;
int count = countNumberOfBST(h);
cout << "The Number of Binary Search Trees of height H consisting of H + 1 nodes: " << count << endl;
return 0;
}``````

Input

``Enter the value of H: 4``

Output

``The Number of Binary Search Trees of height H consisting of H + 1 nodes: 16 ``

Time Complexity

O(log(H)), where â€˜Hâ€™ is the given height.

Since we divide â€˜Hâ€™ by two, every time in the loop until itâ€™s zero, the time complexity is O(log(H)).

Space Complexity

O(1)

As we are not using any additional space.

### What is a Binary Tree?

A Binary Tree is a generic tree with every node having at most two children. A node can have any number of children in generic trees, but in binary trees, a node can only have a left and a right child.

### What are Binary Search Trees?

A Binary Search Tree is a Binary Tree where the value of every node of the tree is larger than the maximum value of its left subtree and lesser than the minimum value of its right subtree.

### Why are Binary Search Trees used?

In Binary Search Trees, the searching becomes very fast compared to the Binary Trees because, at each node, we can judge if we should go to left subtree or right subtree (i.e., if the key value is lesser than the node value, then weâ€™ll go to left subtree to search our key node & if the key value is greater than the node value weâ€™ll proceed to right subtree to search our key node).
The time complexity to search an element is O(log2n), where n is the number of nodes in the binary search tree.

## Conclusion

A fascinating follow-up problem for the above problem would be to build these 2 ^ H trees. On the Coding Ninjas Platform, we have various such problems and blogs. Additionally, Coding Ninjas recently introduced the Coding Ninjas Studio Test Series, a test series developed for acing tech interviews.