Algorithms and Me: Binary Search Tree : Calculate number of trees with N nodes

Given a number N, calculate number of binary search trees that can be formed using number 1 to N as nodes.

Fix one node as the root node, then we calculate number of left sub trees those can be possible with given node i , lets call it l. Then we calculate number of right sub trees possible.lets call it r. So total number of trees which can be formed using given node as root will be (l * r)

Trees[i] =  summation (j = 0 to i) of Tress[j] * Trees[i-j-1]
Tress[0] = Trees[1] =1

int number_of_trees(int n)

{

int i, j;

// Table to store results of subproblems

int Trees[n+1];



// Initialize first two values in table

Trees[0] = Trees[1] = 1;



for (i=2; i<=n; i++)

{

Trees[i] = 0;

for (j=0; j<i; j++)

Trees[i] += Trees[j] * Trees[i-j-1];

}

return Trees[n];

}

Read full article from Algorithms and Me: Binary Search Tree : Calculate number of trees with N nodes