How do I find a minimum subtree?

Asked by steeveage (3

) October 12th, 2009

Given an n-ary tree T where each node has a value V, find the smallest subtree S that contains all values in a list L.

What’s the optimal solution to this? One way I can think of doing this is to do a tree traversal starting from the root to find all values of L and continue to do this for every subtree until it is no longer true. However this is O(n^2), I wonder if there is anything faster.

Observing members: 0

Composing members: 0

3 Answers

Response moderated

This is why I don’t do phylogenetics! :) But really, aren’t all questions like this incredibly slow to answer? That’s why it takes so much computer power to run trees. I’m a biologist, not a math person, so I don’t have any techniques for you to try, but… yeah. I think it’s supposed to take a long time – if you want to get the best tree, that is.

fireinthepriory (7440

)“Great Answer” (0

) Flag as…

I would work the problem backwards. Start with a pair of values and trace backwards to find a common ancestor. The two paths to the ancestor are part of the tree. Now take the common ancestor and one of the other values and find the common ancestor, and so on.

LostInParadise (32278

)“Great Answer” (0

) Flag as…