Velocity Reviews > C++ > BST permutations

# 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

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

jason.s.turner@gmail.com
Guest
Posts: n/a

 03-03-2006
Sorry...and thanks!

Jason

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.