Determine Unique Binary Search Trees

[GregT]

Hello,
I am a student and one of our questions is:

"How many different binary tree search trees can store the keys { 1,2,3,..., 10} ?"
I know that there is a formula to calculate the answer, but I was unable to correctly copy it down in class and my professor is rather busy. Can anyone provide me with the equation to solve this question?

Thanks,
Greg

[nspils]

If you are randomly presented randomly ordered sets to place in a search tree, wouldn't it be the permutations of {1, .., 10}? P(n,r) = n!/(n-r)! P(10,10) = 10!/1 = 3628800

[GregT]

Thank you for your help. I will run that by the professor and see if that is correct.

[feyyaz]

If you are randomly presented randomly ordered sets to place in a search tree, wouldn't it be the permutations of {1, .., 10}? P(n,r) = n!/(n-r)! P(10,10) = 10!/1 = 3628800

It's not correct!
We can create lots of bst's which are the same shape but in a different way.
Example
first insertion order: 5, 4, 3, 2, 1, 6, 7, 8, 9, 10
second insertion order: 5, 6, 4, 7, 8, 3, 2, 1, 9, 10
Different orders but the same shape!

I don't remember how to calculate the exact number , but for sure that is not correct, don't use it

[Kinda Electroni]

You said:
It's not correct!
We can create lots of bst's which are the same shape but in a different way.

I have tried hard to see your point, but I failed.

nspils says:
If you are randomly presented randomly ordered sets to place in a search tree, wouldn't it be the permutations of {1, .., 10}? P(n,r) = n!/(n-r)! P(10,10) = 10!/1 = 3628800

There are many possibilites and this is the formula.

What is your complain?

[nspils]

I see feyyaz's point and the number 3628800 just never felt right [even as I wrote it]. Looking an implementation I see that if we get a certain run of numbers less than (or greater than) the root in a particular order, no matter where within the permutation those individual numbers occur, the organization of the subtree will be exactly the same. So
5-1-6-2-7-3-8-4-9-10
will be a different permutation but the same BST as
5-6-1-7-2-8-3-9-4-10
and
5-6-7-8-9-10-1-2-3-4

So there IS something more to the formula than just a permutation ... has to do with ordering and my head will hurt if I go that far into the recesses of my "discrete math" experience to dig that one out right at the moment ...

So, thanks, feyazz for bringing me back to looking more precisely at this question.

[Kinda Electroni]

If we have only one digit, we will have 10^1=10 possibilities.
If we have two digits, we will have 10^2=100 possibilities.
If we have tree digits, we will have 10^3=1000.
In our case, we have 10 digits then
We have 10^10.
Do you agree with me?

[feyyaz]

Kinda Electroni,
Your self-confidence made me begin to suspect on it ,
and nspils reexplained my point, thanks

I now have the formula for the problem

Number of different binary search trees created from an n size list:
( 1 / (n+1) ) * P( 2n, n )

I tested it with a few values, it works!

[feyyaz]

If we have only one digit, we will have 10^1=10 possibilities.
If we have two digits, we will have 10^2=100 possibilities.
If we have tree digits, we will have 10^3=1000.
In our case, we have 10 digits then
We have 10^10.
Do you agree with me?

I didn't get it, what digit?
Or are we talking about something different?

[nspils]

Pretty convoluted formula, but my gut tells me it is accurate (in the ballpark of what feels right). Thanks, feyyaz, for verifying it.

Electroni: with permutations the operation is factorial, not exponential. 1 way to arrange 1 item, 2 ways to arrange 2 items, 6 ways to arrange 3 items (1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1) not 9 ... And, with permutations of certain number of values in groups of a certain size [P(n,r)], the number is n!/(n-r)!

[Kinda Electroni]

I got it now.