Count Binary Search Trees created from N unique elements

The Dynamic Programming Solution

We have already found the recurrence relation and the sub problems which can contribute in solving the major problem.

To define it in terms of DP, we have to calculate the sum of all the trees for each k as root. Let us start with a table with N columns and N+1 rows. The N+1th row is to store the sum of each column.

Let us have the number of elements as the columns which means all the calculation done on the first column will consider that we have only one element to build the BST, similarly all the calculations done on column 6 will assume that we have a total of six elements to create the BST.

Let us define what a row means or what a cell (intersection of column and row means). A given cell C(4, 6) contains the count of trees which can be made by 6 unique elements given the 4th element is chosen to be the root.

All the cells in that column which has a row value greater than 6 would be zero. This is because, if the total elements available is six, we cannot choose any seventh number as root.

Similarly we will populate the whole column for a given number N and at the end take a sum total of the entire column. That will give the total number of BSTs for N unique elements.

To begin with we already know that for one element the number of trees possible is 1.

So we populate all the cells in the first column with 0 and all the cells in the first row with 1. We start populating one column at a time, which is pretty unusual compared to the traditional loops where we used to populate a row at a time.

C[j][i] = C[N+1][i-j] * C[N+1][j-1]. Let us evaluate this for i = 4 and j = 4 and N = 10
C[4][4] = C[11][0] * C[11][3]
C[4][4] = 1 * 5 = 5

and so on.

Below is the pseudo code for the same:
pseducode2
each cell p in a column K contains a value which is sum of the left trees and the right trees if pth element is the root.

Source Code

Below is the table formed for DP.
dptable

It is really easy to find out how the table is populated, still if there is any issues, please write a comment and I will try to explain in more detail.

Analysis

If we look the above code we see that the space complexity is N * N = N2 to store the complete table. Talking about the time complexity, it is O(N2) for populating the table.

Conclusion

In this article we discussed a very important problem asked in most of the good interviews and various solutions possible. Now we know how to find the total number of BSTs possible with N unique numbers. These numbers are also called Catalan Numbers and there is a prettier formula to find that out.
formula

Hope this helps, happy reading. Stay connected and stay Subscribed