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):
    toVisit = [t]
    while len(toVisit) > 0:
     c = toVisit[0]
     if type(c) is int:
      print c
     else: 
      print c[0]
      toVisit.append(c[1])
      if len(c) > 2: toVisit.append(c[2])
     toVisit = toVisit[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)

Answer 2

It depends on whether you want to do Depth-First or Breadth-First traversal. Depth-first is the easiest to implement via recursion. With Breadth-first you need to keep a queue of nodes to expand in the future.

Answer 3

If you have a fixed amount of memory dedicated to the stack, as you often do (this is especially a problem in many Java JVM configurations), recursion may not work well if you have a deep tree (or if recursion depth is high in any other scenario); it will cause a stack overflow. An iterative approach, pushing nodes to visit onto a queue (for BFS-like traversal) or stack (for DFS-like traversal) has better memory properties in several ways, so if this matters, use an iterative approach.

The advantage of recursion is simplicity/elegance of expression, not performance. Remembering that is the key to choosing the appropriate approach for a given algorithm, problem size, and machine architecture.

Answer 4

Actually you should use queue for breadth first search and stack for depth first search, and run your algorithm from a while loop. Making recursive function calls can drag your program significantly if you do simple operations while traversing, and may cause a stack overflow, but these days you would need to try really hard to see one.

Just have a hash on the side to keep track of already visited nodes in case it is not a tree but a well connected graph.