Iterative tree walking

Question

It's been quite a while since I took data structures and algorithms in college, so I was surprised recently by a suggestion that recursion may not be the way (tm) to do tree traversal. For some reason iterative, queue based traversal has not been a technique that I've ever used.

What, if any, are the advantages of iterative vs. recursive traversal? In what situations might I use one rather than the other?

Answer 1

If you are doing a breadth first search the natural implementation is to push nodes into a queue, not to use recursion.

If you are doing a depth first search then recursion is the most natural way to code the traversal. However, unless your compiler optimizes tail recursion into iteration, your recursive implementation will be slower than an iterative algorithm, and will die with a stack overflow on a deep enough tree.

Some quick Python to illustrate the difference:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))
def bfs(t):
    to_visit = [t]
    while len(to_visit) > 0:
        c = to_visit[0]
        if type(c) is int:
            print c
        else: 
            print c[0]
            to_visit.append(c[1])
            if len(c) > 2: to_visit.append(c[2])
        to_visit = to_visit[1:]

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

bfs(t)
dfs(t)