Total number of possible Binary Search Trees with n nodes

Introduction

As we know,there can be more than one BST possible with a given set of elements. This article addresses  about it. How many Binary Search Trees are possible for a given set of N elements? Here we are only discussing the concern when the elements given  are unique. Hence, we will count binary search trees created from N unique elements.

  Solving the problem

we will solve such problems starting from the known facts, there is no point creating all possible BSTs with the N given elements and then answer. Let us understand it in a bottom up approach. What does the bottom up approach suggests?
Question 1: Can we say the answer for N = 0?
Question 2: Can we say the answer for N = 1?
Question 3: Can we say the answer for N = 2?
Question 4: Is there any relation in the patterns?
Question 5: Is there a solution for N = k which can contribute to the solution of N = k+j,where j is some number >=1 ?
If  answer of these questions are yes ,then we can say that this is a programming problem which can be solved either by recursion or Dynamic Programming. Because this problem is satisfying all the criteria of dynamic programming.
So let us take a set of numbers, fairly randomly distributed so that we get a beautiful BST. We will answer all the questions listed above:

Let's assume we are given  9 nodes .

Answer 1: When N = 0 then there is no tree or I can say an empty tree,or we can say a tree with root is null, hence total number of possible BSTs is 1
Answer 2: When N = 1 then there is only one tree, and that is the root as below, so the number of trees = 1




Answer 3: When N = 2 then there are two trees possible:
a) With 6 as root and
b) With 10 as root
So the number of trees = 2

Answer 4: When N = 3 then we will have following options:
a) With 6 as root
b) With 10 as root and
c) With 13 as root.
Then we see that when 6 is the root then 10 and 13 lie on the right side of the root. That means there are as many possibilities as we had with N = 2 same as the Answer 3.
Similarly when 10 is the root, 6 lies in the left and 13 on the right of the root. So, we have those many possibilities on each side as many we had when N = 1 same as the Answer 2. But we must also realize that for each possibility of left we can have all the possibility in the right or vice versa. In simple words the number of trees formed from the elements in the right is independent of the number of trees formed from the elements in the left. So the total number of trees will be a product of the total left trees and total right trees.
To explain it more, for each tree of the left we can have all possible trees in the right.
Similarly when 13 is the root, 6 and 10 lie on the left side of the root, Than means there are as many possibilities as we had with N = 2 same as Answer 3.
Hence total number of trees possible is 2 + 1 * 1 + 2 = 5. So there is a pattern.

Answer 5: We also saw in answer 4 that the solutions of the smaller problems (for lower values of N) can add up in solving the bigger problem (with higher values of N).
Now assume we are given N = 4.  how do we solve the problem , it will be same as the one we solved in Answer 4.
We will consider each element as the root once and so we will come up with 4 cases, then we find the number of trees possible in each case and add up total number of trees from each case.

Generating the Algorithm and Code snippet -Part2