Determine Unique Binary Search Trees


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 11 of 11

Thread: Determine Unique Binary Search Trees

  1. #1
    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. #2
    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. #3
    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. #4
    Join Date
    Mar 2007
    Posts
    4
    Quote 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. #5
    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. #6
    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. #7
    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. #8
    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. #9
    Join Date
    Mar 2007
    Posts
    4
    Quote 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. #10
    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. #11
    Join Date
    May 2005
    Location
    Ontario, Canada
    Posts
    173

    Thank you

    I got it now.

Similar Threads

  1. Binary and Linear Search
    By ForlornSpawn in forum Java
    Replies: 1
    Last Post: 04-07-2006, 03:43 PM
  2. Binary Search Tree Search algorithm
    By spazzzer in forum Java
    Replies: 1
    Last Post: 03-20-2006, 06:45 PM
  3. Search algorithm of the Binary Search Tree
    By spazzzer in forum Java
    Replies: 6
    Last Post: 03-20-2006, 03:37 AM
  4. Binary Search trees
    By Tom in forum VB Classic
    Replies: 0
    Last Post: 12-02-2000, 01:24 PM
  5. Binary Search trees
    By Tom in forum Java
    Replies: 0
    Last Post: 12-02-2000, 01: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
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

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