CareerCup

public static int catalanNumber(int n) {
		if (n == 1||n==0)
			return 1;
		if (n == 2)
			return 2;
		int sum = 0;
		for (int i = 0; i < n; i++)
			sum = sum + catalanNumber(i) * catalanNumber(n - i - 1);
		return sum;
	}

@Ram :
* Assume u have n nodes
* the left subtree has i nodes
* the right subtree will have n-i-1 nodes
Let
T(i) the number of trees for the left subtree then
T(n-i-1) will the number of subtrees for the right

Total number of trees will be T(i)*T(n-i-1) for all i belongin to 0 to n-1

The recurssion is what i have coded above wothout DP

Without using catalan number :
Let A[] contain the nodes in sorted order.

int numberOfTrees(int[] A, int start, int end) {
int count;
if (start == end) return 0; //0 nodes
if (start+1 == end) return 1; //1 node
if (start+2 == end) return 2; //2 nodes
for (int i = start; i < end; i++) {
int left += numberOfTrees(A, 0, start);
int right += numberOfTrees(A,start+1, A.length);
count += left*right;
}
return count;
}

number of trees can be known by calling numberOfTrees(A,0,A.length)

The array has been taken in sorted order, so that the binary search trees are formed, which will be different in all the cases, and hence there would be no overlapping of structurally same binary trees and at the same time, take into

catalan number，you can calculate use dynamic programming

uses DP :

static HashMap<Integer, Integer> hmap=new HashMap<Integer,Integer>();
	public static int catalanNumber(int n) {
		if (n == 1||n==0)
			return 1;
		if (n == 2)
			return 2;
		if(hmap.containsKey(n))
			return hmap.get(n);
		int sum = 0;
		for (int i = 0; i < n; i++)
			sum = sum + catalanNumber(i) * catalanNumber(n - i - 1);
		hmap.put(n,sum);
		return sum;
	}

How is catalan numbers a solution?

Wiki says catalan gives the number of "full" binary trees. The set of "full" binary trees with n nodes is a subset of all structurally different binary trees.

USING DP

int difftrees(int n)
{

int arr[n+1];
arr[0]=1;
arr[1]=1;
arr[2]=2;

int i,j;
	for(i=3;i<=n;i++)
		{
			arr[i]=0;		
			for(j=0;j<=i-1;j++)
			arr[i]+= (arr[j]*arr[i-1-j] );
		}

return arr[n];

}

const int CatalanNos[12]={1,1,2,0};
long int catalan(int n){
if(n == 0 || n == 1)
return 1;
if(n == 2)
return 2;
if(CatalanNos[n] == 0)
{
long int sum = 0;
for (int i = 0; i < n; i++)
sum = sum + catalan(i) * catalan(n - i - 1);
return sum;
} else {
return CatalanNos[n];
}
}

Can you please explain it ? And without catalan no how can we do it ?