DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Determine Unique Binary Search Trees

1. Registered User
Join Date
Mar 2007
Posts
2

## 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

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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

3. Registered User
Join Date
Mar 2007
Posts
2
Thank you for your help. I will run that by the professor and see if that is correct.

4. Registered User
Join Date
Mar 2007
Posts
4
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!/(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

5. Registered User
Join Date
May 2005
Location
Ontario, Canada
Posts
173

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

There are many possibilites and this is the formula.

What is your complain?

6. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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.

7. Registered User
Join Date
May 2005
Location
Ontario, Canada
Posts
173

## 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?

8. Registered User
Join Date
Mar 2007
Posts
4
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!

9. Registered User
Join Date
Mar 2007
Posts
4
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?

10. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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)!

11. Registered User
Join Date
May 2005
Location
Ontario, Canada
Posts
173

## Thank you

I got it now.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source