# BST permutations

Discussion in 'C++' started by jason.s.turner@gmail.com, Mar 3, 2006.

1. ### Guest

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

, Mar 3, 2006

2. ### mlimberGuest

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-lite/how-to-post.html#faq-5.9). Try
comp.programming or similar.

Cheers! --M

mlimber, Mar 3, 2006

3. ### Guest

Sorry...and thanks!

Jason

, Mar 3, 2006
4. ### Mark PGuest

[OT] Re: BST permutations

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.

Mark P, Mar 4, 2006