How do I traverse a tree without using recursion?

Question

I have a very large in memory node tree and need to traverse the tree. Passing the returned values of each child node to their parent node. This has to be done until all the nodes have their data bubble up to the root node.

Traversal works like this.

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

This works fine, but I'm worried that the call stack limits the size of the node tree.

How can the code be rewritten so that no recursive calls to Execute are made?

Answer 1

Here is a general purpose tree traversal implementation that doesn't use recursion:

public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

In your case you can then call it like so:

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

Use a Queue instead of a Stack for a breath first, rather than depth first, search. Use a PriorityQueue for a best first search.

Answer 2

If you have an estimate for the depth of your tree beforehand, maybe it is sufficient for your case to adapt the stack size? In C# since version 2.0 this is possible whenever you start a new thread, see here:

http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx

That way you can keep your recursive code, without having to implement something more complex. Of course, creating a non-recursive solution with your own stack may be more time and memory efficient, but I am pretty sure the code will not be as simple as it is for now.

Answer 3

You can't traverse a data structure in the shape of a tree without using recursion - if you don't use the stack frames and function calls provided by your language, you basically have to program your own stack and function calls, and it is unlikely that you manage to do it within the language in more efficient manner way than the compiler writers did on the machine that your program would run on.

Therefore, avoiding recursion for fear of running into resource limits is usually misguided. To be sure, premature resource optimization is always misguided, but in this case it is likely that even if you measure and confirm that memory usage is the bottleneck, you will probably not be able to improve on it without dropping down to the level of the compiler writer.