16

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.

Binary search trees over elements 1, 2, 3

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
siddstuff
  • 1,215
  • 4
  • 16
  • 37
  • Probably [related](http://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib). – G. Bach Apr 14 '13 at 21:55

3 Answers3

42

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

enter image description here

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 Cn, and therefore the number of possible BSTs is given by the nth Catalan number.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 1
    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. – Sukhanov Niсkolay Nov 23 '13 at 10:32
  • 1
    @SukhanovNiсkolay The number of BSTs are still 5 for 10,10,10. The tree shape will be different. – rents Sep 01 '17 at 06:17
9

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

dharam
  • 7,882
  • 15
  • 65
  • 93
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

Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
  • It might be good to mention that this recurrence solves to the nth Catalan number. – templatetypedef Apr 14 '13 at 22:01
  • @templatetypedef: Do you know how to derive the catalan number formula starting from the sum I have shown? – Andrew Tomazos Apr 14 '13 at 22:06
  • @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. – G. Bach Apr 14 '13 at 22:11
  • 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. – Andrew Tomazos Apr 14 '13 at 22:12
  • @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. – templatetypedef Apr 14 '13 at 22:20