Iterative Tree Traversal

When dealing with a tree (i.e., hierarchical) data structure, recursion is typically the first tool a grizzled veteran programmer will reach for from his trusty toolbelt. After grasping air or worse, he will of course remember that recursion is not a physical tool, but a development approach that involves self-referential code.

Consider the following method, which will traverse a Tree data structure and perform some operation on each node:

Visit(Tree t)
{
  DoSomethingExcitingWith(t);

  foreach (Tree child in t.children)
  {
    Visit(child);
  }
}

This is generally a concise and appropriate way to implement a tree traversal algorithm. However, in cases involving trees with an especially deep structure, recursion can use too much memory, since each method invocation requires the allocation of a new stack frame. Such times call for drastic, tedious measures, otherwise known as iteration. I don't recall ever seeing a tree traversal algorithm implemented iteratively in practice, but here is one approach to do so:

IterVisit(Tree t)
{
  Stack s = new Stack();
  s.Push(t);

  while (s.Size() > 0)
  {
     t = s.Pop();
     DoSomethingExcitingWith(t);

     foreach Tree child in t.children
     {
       s.Push(child);
     }
  }
}

One interesting fact about this iterative implementation is that the use of a Stack implies a depth-first tree traversal, while simply changing to a Queue configures the algorithm to use a breadth-first traversal.