Given a sorted integer array, how may Binary Search trees can be formed from it? - Stack Overflow

algorithm - Given a sorted integer array, how may Binary Search trees can be formed from it? - Stack Overflow
Given a sorted integer array, how may Binary Search trees can be formed from it? 

Each tree can be thought of as two trees with a parent root node. If you know the number of possible combinations of the two children branches separately, the total combinations having that root node is the product of the children combinations.

We can begin building up a higher count solution by solving the lower count instances first.

I will use C(n) to represent the total possible combinations of n nodes, the Catalan Number.

Hopefully these two are obvious:

C(0) = 1
C(1) = 1

C(2) is also fairly obvious, but it can be built, so let's do that. There are two ways to choose the root node. One leaves a child count (left:right) of 1:0 and the other 0:1. So, the first possibility is C(1)*C(0) = 1*1 = 1. And the second is C(0)*C(1) = 1*1 = 1. Summing those together gives us

C(2) = 2

Nothing too exciting yet. Now let's do 3 nodes. There are 3 ways to choose the root node and, hence, 3 child groupings. Your possible groups are 2:0, 1:1 and 0:2.

Based on our prior defintions, C(3) can be written as C(2)*C(0) + C(1)*C(1) + C(0)*C(2) = 2*1 + 1*1 + 1*2 = 2+1+2 = 5.

C(3) = 5

4 nodes has child groupings of 3:0, 2:1, 1:2 and 0:3. So, C(4) can be written as C(3)*C(0) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3) = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14.

C(4) = 14

BSTCount(0) = 1
BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(n-i)

http://stackoverflow.com/questions/1352776/the-possible-number-of-binary-search-trees-that-can-be-created-with-n-keys-is-gi

int countTrees(int numkeys){
if(numkeys>1){
    int i =1;
    int sum=0;

    for(i= 1; i <=numkeys; i++){

        int lcount = countTrees(i-1);
        int rcount = countTrees(numkeys-i);
        sum += lcount*rcount;
    }
    return(sum);
}else
    return(1);

}

Read full article from algorithm - Given a sorted integer array, how may Binary Search trees can be formed from it? - Stack Overflow