2

I have a non-binary tree. I want to randomly find a "sub-trees" that are connected from root to leaf which must have at least n leaf-nodes (leaf-nodes of sub-tree must be leaf-nodes of given tree). For example: given a tree as below

           *A
          /   \
         B     C
        / \     \
      *E   D    *F
            \
             *J

n = 2
A random sub-tree that contains 2 leaf-nodes could be:

            A
          /   \
         B     C
        /       \
       E         F

or

            A
          /   \
         B     C
          \     \
           D     F
            \
             J

or

            A
          /   
         B     
        / \     
       E   D     
            \
             J

I don't need to get all possible sub-trees, just randomly get it with a given tree and n

  • 1
    In addition to the comment of @Snowman, your question is possibly too broad – Benni Jan 8 '15 at 8:01
  • Count the number of leaf nodes in the given tree. If this number is greater or equal to n, return the tree itself. Otherwise, there is no subtree with at least n leaf nodes. – mgoeminne Jan 9 '15 at 9:19
1

Randomly choose n leaf nodes. Return the tree that contains those leaf nodes and their ancestors.

Whenever you say "random", you should specify what probability distribution you want. Unless you nail down the probability distribution, any of these "solutions" will meet your needs:

  1. Always pick the leftmost n leaves.
  2. Always pick the rightmost n leaves.
  3. Always pick the middle n leaves.
  4. Visit all the leaves in some desired order. Put each one at the end of a list. If the list now contains more than n nodes, delete one of them at random.
  5. Make a list of all the leaves, and then repeatedly discard one at random until there are only n left.
  6. Choose a random number from 1 to 5. Use the corresponding method from the above list.

Notice that the word "random" appears several times in the above. Each of these instances of "random" should be qualified by its probability distribution.

But especially notice that randomly picking n items from a larger set is a completely separate sub-problem that has nothing to do with trees. First you solve that, then you come back to the trees domain to build the tree that has your chosen leaf nodes.

Try solving each of these sub-problems. I think you'll find that neither is terribly difficult, once you put the other sub-problem temporarily out of your mind.

Otherwise, if you're trying to build the tree while you're picking the leaves to go into it, you're going to drive yourself mad.

  • I don't really get your when you say "Unless you nail down the probability distribution, any of these "solutions" will meet your needs...Always pick the leftmost/rightmost/middle n leaves.". How can my solution could be random when it always return the same output for a given input. The "solutions" 4,5,6 for me are quite the same and acceptable despite I don't really understand the 4th. – Hung Ton Jan 8 '15 at 6:40
  • 1
    You don't understand the implications when you use the word "random". What you probably meant by "random" is "amongst all possibilities, choose one, where any of the possibilities is equally likely to be chosen", i.e. what's known as a uniform probability distribution (like using a fair die). But you didn't say that explicitly. It is possible to use other probability distributions (i.e. choosing you want to use a loaded - biased - die). "Always pick the leftmost n leaves" is using a different probability distribution where the die is so loaded that it always chooses the same way. – Alnitak Jan 8 '15 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.