Nicollet.Net

This message is a rehash of an earlier post on Stack Overflow. It’s self-sufficient enough to be featured here, and I like to keep my content where I can see it If you’re not a computer genius, you can wait until next Monday for an article that can be read by standard issue humans.

The premise is to take a standard tree traversal function (which is a recursive algorithm) and implement it without recursion. The recursive version is:

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

Try doing it on your own, then start reading the solution below once your brain is fried.

The solution

This is a clear case of tail recursion, so you can easily turn it into a while-loop.

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

You’re left with a recursive call. What the recursive call does is push a new context on the stack, run the code from the beginning, then retrieve the context and keep doing what it was doing. So, you create a stack for storage, and a loop that determines, on every iteration, whether we’re in a “first run” situation (non-null node) or a “returning” situation (null node, non-empty stack) and runs the appropriate code:

traverse(node):
  stack = []
  while !empty(stack) || node != None do:
    if node != None do: // this is a normal call, recurse
      push(stack,node)
      node = node.left
    else // we're returning: pop and print the current node
      node = pop(stack)
      print node.value
      node = node.right
    endif
  endwhile

The hard thing to grasp is the “return” part: you have to determine, in your loop, whether the code you’re running is in the “entering the function” situation or in the “returning from a call” situation, and you will have an if/else chain with as many cases as you have non-terminal recursions in your code.

In this specific situation, we’re using the node to keep information about the situation. Another way would be to store that in the stack itself (just like a computer does for recursion). With that technique, the code is less optimal, but easier to follow

traverse(node):
  // entry:
  if node == NULL do return
  traverse(node.left)
  // after-left-traversal:
  print node.value
  traverse(node.right)

traverse(node):
   stack = [node,'entry']
   while !empty(stack) do:
     [node,state] = pop(stack)
     switch state:
       case 'entry':
         if node == None do: break // return
         push(stack,[node,'after-left-traversal']) // store return address
         push(stack,[node.left,'entry']) // recursive call
         break
       case 'after-left-traversal':
         print node.value;
         // tail call : no return address
         push(stack,[node.right,'entry']) // recursive call
      end
    endwhile