algorithm - Number of binary search trees over n distinct elements

Question

How many binary search trees can be constructed from n distinct elements? And how can we find a mathematically proved formula for it?

Example: If we have 3 distinct elements, say 1, 2, 3, there are 5 binary search trees.

Answer 1

Given n elements, the number of binary search trees that can be made from those elements is given by the nth Catalan number (denoted C_n). This is equal to

Intuitively, the Catalan numbers represent the number of ways that you can create a structure out of n elements that is made in the following way:

• Order the elements as 1, 2, 3, ..., n.
• Pick one of those elements to use as a pivot element. This splits the remaining elements into two groups - those that come before the element and those that come after.
• Recursively build structures out of those two groups.
• Combine those two structures together with the one element you removed to get the final structure.

This pattern perfectly matches the ways in which you can build a BST from a set of n elements. Pick one element to use as the root of the tree. All smaller elements must go to the left, and all larger elements must go to the right. From there, you can then build smaller BSTs out of the elements to the left and the right, then fuse them together with the root node to form an overall BST. The number of ways you can do this with n elements is given by C_n, and therefore the number of possible BSTs is given by the nth Catalan number.

Hope this helps!