What is the most efficient way to cross a tree in Python?

Question

Assuming I have a list of objects that have the following fields

parent

Value

and this defines a tree structure similar to a directory tree.

I want to go through the list in pre-order. What is the most effective way?

Usually in other (more imperative) languages, I would sort through the values, find those who have no parents, and then for each, iterate again for each object whose parent is the one I'm looking at, etc., but there are is there a more convenient way to do this in Python?

Answer 1

- :

children = {}
for obj in tree:
    children.setdefault(obj.parent, []).append(obj)

def preorder(root, children):
    yield root.value
    for child in children.get(root, []):
        for value in preorder(child, children):
            yield value

for root in children[None]:
    for value in preorder(root, children):
        print value

collections.defaultdict.