Traversing arbitrarily large binary tree inorder

Question

I'm stuck at finding a solution. C#, .NET 4.0, VS2010

I can easily write a recursive one, but can't for the life of me figure out something that won't overflow the stack if the tree is arbitrarily large.

This is a binary tree question, and i am trying to write a

public IEnumerable<T> Values()

method.

Here is the full code in case you are interested: http://pastebin.com/xr2f3y7g

Obviously, the version currently in there doesn't work. I probably should mention that I am a newbie in C#, transitioning from C++.

Answer 1

Assuming the tree is anywhere near balanced, its maximum depth is log2(n), so you'd need a huge tree to overflow the stack.

You can transform any recursive algorithm into an iterative one, but in this case, it will likely require either backward pointers or an explicit stack, both of which look expensive.

Having said that, recursion is typically not so great in .NET because any local variables in calling instances of a method cannot be GC'ed until the stack gets unwound after the terminating condition. I don't know whether the JIT will automatically optimize tail-end recursion to make it iterative, but that would help.

Answer 2

Here is a method for inorder traversal, that uses explicit stack. The stack is created on the heap, so it can be much larger, than the stack the processor uses.

public IEnumerable<T> Values()
{
    Stack<Node> stack = new Stack<Node>();
    Node current = this.root;
    while(current != null)
    {
        while(current.leftChild != null)
        {
            stack.Push(current);
            current = current.leftChild;
        }
        yield return current.data;
        while(current.rightChild == null && stack.Count > 0)
        {
            current = stack.Pop();
            yield return current.data;
        }
        current = current.rightChild;
    }

}

If you can't use a stack and your nodes happen to have parent pointers, you can try solutions from this question