Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > BST permutations

Reply
Thread Tools

BST permutations

 
 
jason.s.turner@gmail.com
Guest
Posts: n/a
 
      03-03-2006
I have spent hours on this problem and cannot get it, any help would be
appreciated:

A binary search tree using n distinct integers 1, 2, ..., n. There
are n! possible initial orderings of the n numbers. How many of the n!
permutations will result in a perfectly balanced binary search tree?
Assume that n =2^k -1 for some positive integer k.

I was given a hint: 1 node = 1 permutation, 3 nodes = 2 permutations,
7 nodes = 80 permuations.

Thanks,

Jason

 
Reply With Quote
 
 
 
 
mlimber
Guest
Posts: n/a
 
      03-03-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> I have spent hours on this problem and cannot get it, any help would be
> appreciated:
>
> A binary search tree using n distinct integers 1, 2, ..., n. There
> are n! possible initial orderings of the n numbers. How many of the n!
> permutations will result in a perfectly balanced binary search tree?
> Assume that n =2^k -1 for some positive integer k.
>
> I was given a hint: 1 node = 1 permutation, 3 nodes = 2 permutations,
> 7 nodes = 80 permuations.
>
> Thanks,
>
> Jason


Off-topic
(http://www.parashift.com/c++-faq-lit....html#faq-5.9). Try
comp.programming or similar.

Cheers! --M

 
Reply With Quote
 
 
 
 
jason.s.turner@gmail.com
Guest
Posts: n/a
 
      03-03-2006
Sorry...and thanks!

Jason

 
Reply With Quote
 
Mark P
Guest
Posts: n/a
 
      03-04-2006
(E-Mail Removed) wrote:
> I have spent hours on this problem and cannot get it, any help would be
> appreciated:
>
> A binary search tree using n distinct integers 1, 2, ..., n. There
> are n! possible initial orderings of the n numbers. How many of the n!
> permutations will result in a perfectly balanced binary search tree?
> Assume that n =2^k -1 for some positive integer k.
>
> I was given a hint: 1 node = 1 permutation, 3 nodes = 2 permutations,
> 7 nodes = 80 permuations.
>
> Thanks,
>
> Jason
>


What does this mean? How do you map a permutation of the integers onto
a BST? There is only one balanced binary search tree for these n numbers.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
LL TO BST puzzlecracker C++ 2 01-19-2005 11:10 PM
Applications of stacks/queues/trees/heap/BST Ice C++ 4 12-19-2004 06:04 PM
BST: remove less than Ridimz C++ 8 10-07-2003 01:40 AM
BST Rupert harrison C++ 2 09-15-2003 08:38 AM
BST & recursion Andrew Edwards C++ 12 08-04-2003 10:54 AM



Advertisments