Recursive Iterators made Iterative

So I've been thinking about this, and although it seems like CS101 to transform a recursive algorithm into an iterative one, and example might be worth while.    The natural one to attack would be the generic binary tree traversal iterator.  So here goes!

My first thought would be to use the new Queue class to keep track of parent nodes:

public class BinaryTree<DataType> {    public DataType Data;    public BinaryTree LeftChild;    public BinaryTree RightChild;    public IEnumerable<DataType> InOrder {        get {            // if we were smart and had the data            // we could set the initial capacity to our max depth            Stack<BinaryTree<DataType>> stack = new Stack();
            for (BinaryTree<DataType> current = this;                 current != null || stack.Count > 0;                `` current = current.RightChild)            ``{``                while (current != null) {``                    stack.Push(current);                    current = current.LeftChild;                }                current = stack.Pop();
                yield return current.Data;``            }``        }    }}

If I did everything right, this will only allocate the 1 stack object and enough storage within that for log N references.  And no recursion!

--Grant

Comments

• Anonymous
  August 28, 2010
  I see this is a very old post, but surprisingly, I didn't find anywhere someone who solved this problem of efficient recursive iterators in a generic, easy to use and reusable way as I did in my recent post. If you're still alive ;-), I'd like to hear what you think about my solution... Thanks, Arnon.

• Anonymous
  August 31, 2010
  That does seem to make it easier to write them, but I think it is hiding a lot of the costs.  You have a lot more allocated objects, and a lot more calls.  I think before I went that route, I would try the old fashinoned  recursive iterator because it is neat and clean.  If performance really was a problem, then I'm not sure your solution would be much better, so I would rewrite it as truely iterative as I did here.  Of course I am a little biased... --Grant