CareerCup

int countTrees(int numKeys) { 

  if (numKeys <=1) { 
    return(1); 
  } 
  else { 
    // there will be one value at the root, with whatever remains 
    // on the left and right each forming their own subtrees. 
    // Iterate through all the values that could be the root... 
    int sum = 0; 
    int left, right, root; 

    for (root=1; root<=numKeys; root++) { 
      left = countTrees(root - 1); 
      right = countTrees(numKeys - root); 

      // number of possible trees with this root == left*right 
      sum += left*right; 
    } 

    return(sum); 
  } 
}

The problem can be solved by finding the Catalan number for the value of n...

The formula for finding the Catalan number is (1/(n+1))*(2n C n)... where C is combination...

Using this formula we have, if n = 4, no of BST's possible is 14.
If n = 5, no of BST's possible is 42 and so on...

- Rahul

The number of non-isomorphic ordered binary trees with 5 vertices. 42 as Rahul said.

Its catalan number, The same question was asked to me in an Google interview

int countTrees(int numKeys) { 

  if (numKeys <=1) { 
    return(1); 
  } 
  else { 
    // there will be one value at the root, with whatever remains 
    // on the left and right each forming their own subtrees. 
    // Iterate through all the values that could be the root... 
    int sum = 0; 
    int left, right, root; 

    for (root=1; root<=numKeys; root++) { 
      left = countTrees(root - 1); 
      right = countTrees(numKeys - root); 

      // number of possible trees with this root == left*right 
      sum += left*right; 
    } 

    return(sum); 
  } 
}

Can be solved, by first calculating for tree with 1 node, then tree with 2 nodes, then tree with 3 nodes, so on so forth. Like for tree with 3 nodes it can be calculated by assuming first node as root node so there will be 0 node on left side and 2 nodes on right side, then 1 on left and 1 on right , other being 2 nodes on left side and 0 node on right side and adding all.

NT(i, j)
	if(i == j)
		return 1
	for each k from i to j
		v = v+ NT(i, k-1)*NT(k+1, j)
	return v

main
	NT(1, n)

public static void main(String[] args) {
		System.out.println(noOfBSTs(5));
	}
	
	public static HashMap<Integer, Integer> map = 
			new HashMap<Integer, Integer>();
	
	public static int noOfBSTs(int n){
		if(n < 3) return Math.max(0, n);
		Integer cachedResult = map.get(n);
		if(cachedResult != null)
			return cachedResult.intValue();
		int sum = 0;
		for(int root = 0; root < n; root++){
			sum += noOfBSTs(root - 1);
			sum += noOfBSTs(n -1 -root);
		}
		map.put(n, sum);
		return sum;
	}

This code gave me result of 24 for input: 5
Did I do a mistake or this is not actually Catalan Numbers problem?

Regards

its: 2^n - n