<p>I've got a unidirectional tree of objects, in which each objects points to its parent. Given an object, I need to obtain its entire subtree of descendants, as a collection of objects. The objects are not actually in any data structure, but I can easily get a collection of all the objects.</p>

<p>The naive approach is to examine each object in the batch, see if the given object is an ancestor, and keep it aside. This would not be too efficient... It carries an overhead of O(N*N), where N is the number of objects.</p>

<p>Another approach is the recursive one, meaning search for the object's direct children and repeat the process for the next level. Unfortunately the tree is unidirectional... there's no direct approach to the children, and this would be only slightly less costly than the previous approach.</p>

<p>My question: Is there an efficient algorithm I'm overlooking here?</p>

<p>Thanks,</p>

<p>Yuval =8-)</p>

Your question is a little abstract, but
nested sets
(scroll down, might be a little too mysql-specific) might be an option for you. It's extremely fast for read operations, though any modifications are quite complex (and have to modify half the tree on average).
That requires the ability to modify your data structure, though. And I guess if you can modify the structure, you could just as well add references to child objects. If you can't modify the structure, I doubt there's anything faster than your ideas.