There is one BST for one node.
There are 2 BST for 2 nodes.
There are 5 BST for 3 nodes.
There are 14 BST for 4 nodes.
Could anyone draw all the BSTs and induce the relation ship between BST of k nodes and BST of k+1 nodes? And I wonder the induction process. Does anyone share it?
One of the combinatorial interpretations of Catalan numbers (Cn) is the number of non-isomorphic ordered trees with n+1 vertices. http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics
Watch the first 5 minutes of this lecture of Donald Knuth https://www.youtube.com/watch?v=cI6tt9QfRdo&feature=player_detailpage#t=228
result-n-nodes = ((2n)!) / ((n+1)! * n!)