C# Optimization – How to Traverse a Tree Without Using Recursion

coptimizationtrees

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?

Best Answer

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.

Related Topic