GrantRi's WebLog [MS]

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;
            }
        }
    }
}

--Grant