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
    #1
    1. Advertising

  2. mlimber Guest

    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
    #2
    1. Advertising

  3. Guest

    Sorry...and thanks!

    Jason
    , Mar 3, 2006
    #3
  4. Mark P Guest

    [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
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andrew Edwards

    BST & recursion

    Andrew Edwards, Jul 30, 2003, in forum: C++
    Replies:
    12
    Views:
    779
    Karl Heinz Buchegger
    Aug 4, 2003
  2. Rupert harrison

    BST

    Rupert harrison, Sep 15, 2003, in forum: C++
    Replies:
    2
    Views:
    553
    Karl Heinz Buchegger
    Sep 15, 2003
  3. Ridimz

    BST: remove less than

    Ridimz, Oct 4, 2003, in forum: C++
    Replies:
    8
    Views:
    531
    Josh Sebastian
    Oct 7, 2003
  4. Ice
    Replies:
    4
    Views:
    5,008
  5. puzzlecracker

    LL TO BST

    puzzlecracker, Jan 19, 2005, in forum: C++
    Replies:
    2
    Views:
    394
    Joseph Turian
    Jan 19, 2005
Loading...

Share This Page