How do you iterate over a tree?

Question

What is your preferred method of traversing a tree data structure, since recursive method calls can be pretty inefficient in some circumstances. I am simply using a generator like the one above. Do you have any hints to make it faster?

def children(self):
    stack = [self.entities]
    while stack: 
        for e in stack.pop():
            yield e
            if e.entities:
                stack.append(e.entities) 

Here is some test data. The first one is recursive, the second uses the generator:

s = time.time()
for i in range(100000):
    e.inc_counter()
print time.time() - s

s = time.time()
for i in range(100000):
    for e in e.children():
        e.inc_counter_s()
print time.time() - s

Results:

0.416000127792
0.298999786377

Test code:

import random

class Entity():
    def __init__(self, name):
        self.entities = []
        self.name = name
        self.counter = 1
        self.depth = 0

    def add_entity(self, e):
        e.depth = self.depth + 1
        self.entities.append(e)

    def inc_counter_r(self):
        for e in self.entities:
            e.counter += 1
            e.inc_counter_r()

    def children(self):
        stack = [self.entities]
        while stack:
            for e in stack.pop():
                yield e
                if e.entities:
                    stack.append(e.entities)

root = Entity("main")
def fill_node(root, max_depth):
    if root.depth <= max_depth:
        for i in range(random.randint(10, 15)):
            e = Entity("node_%s_%s" % (root.depth, i))
            root.add_entity(e)
            fill_node(e, max_depth)
fill_node(root, 3)

import time
s = time.time()
for i in range(100):
    root.inc_counter_r()
print "recursive:", time.time() - s

s = time.time()
for i in range(100):
    for e in root.children():
        e.counter += 1
print "generator:",  time.time() - s

Answer 1

I can't think of any big algorithmic improvements, but a simple microoptimisation you can make is to bind frequently called methods (such as stack.append / stack.pop) to locals (this saves a dictionary lookup)

def children(self):
    stack = [self.entities]
    push = stack.append
    pop = stack.pop
    while stack: 
        for e in pop():
            yield e
            if e.entities:
                push(e.entities)

This gives a small (~15%) speedup by my tests (using 100 traversals of an 8-deep tree with 4 children at each node gives me the below timings:)

children     :  5.53942348004
children_bind:  4.77636131253

Not huge, but worth doing if speed is important.

Answer 2

Unless your tree is really large or you have really high (real) requirements for speed, I would choose the recursive method. Easier to read, easier to code.