Number of unique BSTs with n nodes in C++

A BST(Binary Search Tree) is a kind of binary tree wherein the left subtree of a node contains nodes with values less than that of the node and the right subtree of the node contains elements with values greater than that of the node. Given n nodes, with values from 1 to n, we are to find the number of unique BSTs that can be formed.

Approach

The first step is selecting the root node. As we can form BSTs using any one of the n nodes as the root node, we have to take all cases into account i.e. make each node the root node one by one, and count the number of BSTs that can be formed using that node as the root node. To count the total number of BSTs that can be formed using the same root node, we have to find the different number of possible left subtrees and right subtrees of that node and multiply the two. We can easily write a recursive code for this.

Code with explanation

#include <iostream>
using namespace std;

int calculatetrees(int n){
    if(n<=1)
        return 1;
    else{
        int leftsubtrees,rightsubtrees,root;
        int ans=0;
        for(root=1;root<=n;root++){
            leftsubtrees=calculatetrees(root-1);
            rightsubtrees=calculatetrees(n-root);
            ans+=leftsubtrees*rightsubtrees;
        }
        return ans;
    }
    
}

int main(){
    
    int n;
    cin>>n;
    cout<<calculatetrees(n)<<endl;
    return 0;
}

The base case of the recursive function is when n is less than or equal to 1.

In both these cases, there can only be one unique BST and hence the function returns 1. If n is greater than 1, the function runs a for loop where the root is set from 1 to n and the function is recursively called for calculating the number of left and right subtrees. Understand that calling the same function on values in a range from 5 to 10 and 1 to 5 is the same, and which is why the for loop runs from 1 to n every time as the range of values doesn’t matter as long as they are consecutive.

The product of the left and right subtrees is added to the answer and the answer is updated at every iteration of the for loop.

Let’s look at a few examples now.

Input

4 
6

Output

14
132