
Determine Unique Binary Search Trees
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

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!/(nr)! P(10,10) = 10!/1 = 3628800

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

Originally Posted by 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!/(nr)! 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

feyyaz
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!/(nr)! P(10,10) = 10!/1 = 3628800
There are many possibilites and this is the formula.
What is your complain?

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
51627384910
will be a different permutation but the same BST as
56172839410
and
56789101234
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.

10^10
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?

Kinda Electroni,
Your selfconfidence 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!

Originally Posted by 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?
I didn't get it, what digit?
Or are we talking about something different?

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!/(nr)!

Similar Threads

By ForlornSpawn in forum Java
Replies: 1
Last Post: 04072006, 02:43 PM

By spazzzer in forum Java
Replies: 1
Last Post: 03202006, 05:45 PM

By spazzzer in forum Java
Replies: 6
Last Post: 03202006, 02:37 AM

By Tom in forum VB Classic
Replies: 0
Last Post: 12022000, 12:24 PM

Replies: 0
Last Post: 12022000, 12:08 PM
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Development Centers
 Android Development Center
 Cloud Development Project Center
 HTML5 Development Center
 Windows Mobile Development Center
