Count binary search trees–Given N nodes, how many structurally BST are possible?

Problem:
This is not a binary tree programming problem in the ordinary sense -- it's more of a math/combinatorics recursion problem that happens to use binary trees. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different  binary search trees are there that store those values?



Solution
Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!
See references for proof and examples.
References:
http://en.wikipedia.org/wiki/Catalan_number

Method 1 - Recursion
Write a recursive function that, given the number of distinct values, computes the number of structurally unique binary search trees that store those values. For example, countTrees(4) should return 14, since there are 14  structurally unique binary search trees that store 1, 2, 3, and 4. The base case is easy, and the recursion is short but dense. Your code should not construct any actual trees; it's just a counting problem.

N=0, count = 1 as we can have a null tree
N = 1 , count = 1, we can have only 1 tree
N =2 , count = 2, trees being

N = 3, count = 5, trees being

N = 4, count = 14, trees being:

/*
 For the key values 1...numKeys, how many structurally unique
 binary search trees are possible that store those keys.  
 Strategy: consider that each value could be the root.
 Recursively find the size of the left and right subtrees.
*/
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);//number of elements in left subtree
                                  //will be less than root
      right = countTrees(numKeys - root);
      // number of possible trees with this root == left*right
      sum += left*right;
    }
    return(sum);
  }
}

Another good resource on this, for those who want to see the video : https://www.youtube.com/watch?v=UfA_v0VmiDg