title: The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?
body: <p>This has been bothering me for a while. I know that given N keys to arrange in the form of a binary search tree, the possible number of trees that can be created correspond to the Nth number from the <a href="http://en.wikipedia.org/wiki/Catalan_number" rel="noreferrer">Catalan sequence</a>. </p>
  
  <p>I have been trying to determine why this is; unable to find anything that might even attempt to explain it intuitively I resort to the collective knowledge of SO. I found other ways to calculate the number of possible trees, but they seemed less intuitive and no explanation was offered beyond how to use it. Plus the wiki page (that link above) even shows an image of the possible tree formations with 3 keys, which would lead me to think there's a nice and neat explanation to be heard (which is, needless to say, not included in the article).</p>
  
  <p>Thanks in advance!</p>