What is the most efficient way to traverse 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 traverse the list in a pre-order fashion. What's the most efficient way?

Normally, in other (more imperative) languages I would iterate the values, finding the ones with no parents, then for each, iterating again for every object whose parent is the one I'm currently looking at and so forth, but is there a cleverer way to do this in Python?

Answer 1

I would first create a more suitable data structure -- capturing the link from a parent to its children:

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

You could also use collections.defaultdict here.