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.

Solution 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!

Solution 2

I am sure this question is not just to count using a mathematical formula.. I took out some time and wrote the program and the explanation or idea behind the calculation for the same.

I tried solving it with recursion and dynamic programming both. Hope this helps.

The formula is already present in the previous answer:

So if you are interested in learning the solution and understanding the apporach you can always check my article Count Binary Search Trees created from N unique elements

Solution 3

Let T(n) be the number of bsts of n elements.

Given n distinct ordered elements, numbered 1 to n, we select i as the root.

This leaves (1..i-1) in the left subtree for T(i-1) combinations and (i+1..n) in the right subtree for T(n-i) combinations.

Therefore:

T(n) = sum_i=1^n(T(i-1) * T(n-i))

and of course T(1) = 1

Comments

[templatetypedef]

It might be good to mention that this recurrence solves to the nth Catalan number.

[Andrew Tomazos]

@templatetypedef: Do you know how to derive the catalan number formula starting from the sum I have shown?

[G. Bach]

@user1131467 This sum should be exactly the number of triangulations of a polygon over n+2 nodes, which is the way I was introduced to Catalan numbers. You fix an edge and let the pivot wander over the other n vertices, which leaves you with two polygons of sizes i-1 and n-i.

[Andrew Tomazos]

It turns out my sum has a name. It is called "Segner's recurrence relation". A google for that plus catalan numbers will reveal the derivation.

[templatetypedef]

@user1131467- The proof of this that I know (using generating functions) is on the Wikipedia website. There's actually several different proofs there, all of which are pretty good.

[Sukhanov Niсkolay]

For example for nodes 10, 10, 10 the number of binary search trees is 1. But the Catalan number is 5. But if all elements is different it's ok i think.

[rents]

@SukhanovNiсkolay The number of BSTs are still 5 for 10,10,10. The tree shape will be different.