Results 1 to 8 of 8

Math Help - Graph Theory:Tree

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Question Graph Theory:Tree

    Given a set of n distinct elements and an unlabeled binary tree of n nodes. In how many ways we can populate the tree with the given set so that it becomes a binary search tree?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Graph Theory:Tree

    I assume the elements that are to become labels are linearly ordered. Have you tried small examples of trees?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: Graph Theory:Tree

    Theres no ordering among the element , then known information is that the elements are distinct.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Graph Theory:Tree

    The definition of the binary search tree assumes that node labels are ordered.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: Graph Theory:Tree

    You just peek any element from the set ,make it root node
    then peek next element and place it at appropriate place based on current elements in the treee and so on..
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: Graph Theory:Tree

    Ans to this question is (1/(n+1)) *(2n chooses n)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Graph Theory:Tree

    Quote Originally Posted by nikhilbhr View Post
    You just peek any element from the set ,make it root node
    then peek next element and place it at appropriate place based on current elements in the treee and so on..
    How exactly do you take the current elements into account to find an appropriate place for the new element?

    The problem statement does not make much sense to me. If a tree is given, then each labeling, viewed as a binary search tree, corresponds to one and only one ordering of the labels (i.e., elements).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: Graph Theory:Tree

    Actually this question is from IIT GATE examination.I was not able to solve this question.I have written the question as it was in the examination
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Every connected graph contains a maximal tree
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 4th 2011, 07:44 AM
  2. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  3. Replies: 6
    Last Post: November 12th 2010, 08:03 AM
  4. graph + tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 5th 2010, 12:27 AM
  5. simple graph is a tree?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 08:45 AM

Search Tags


/mathhelpforum @mathhelpforum