19

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?

  • 8
    You would either have to maintain your own stack to keep track of the nodes, or change the shape of the tree. See stackoverflow.com/q/5496464 and stackoverflow.com/q/4581576 – Robert Harvey Jan 30 '14 at 21:13
  • 1
    I also found a lot of help at this Google Search, specifically Morris Traversal. – Robert Harvey Jan 30 '14 at 21:17
  • @RobertHarvey thanks Rob, I wasn't sure what terms this would go under. – Reactgular Jan 30 '14 at 21:19
  • 2
    You might be surprised at the memory requirements if you did the math. For example, a perfectly balanced teranode binary tree only needs a stack 40 entries deep. – Karl Bielefeldt Jan 30 '14 at 21:37
  • @KarlBielefeldt That assumes the tree is perfectly balanced though. Sometimes you need to be modeling trees that aren't balanced, and in that case it's very easy to blow the stack. – Servy Jan 30 '14 at 21:47
26

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.

  • Am I correct in thinking this will just flatten the tree into a collection? – Reactgular Jan 30 '14 at 21:56
  • 1
    @MathewFoscarini Yes, that's its purpose. Of course, it doesn't need to necessarily be materialized into an actual collection. It's just a sequence. You can iterate over it to stream the data, without needing to pull the entire data set into memory. – Servy Jan 30 '14 at 21:56
  • I don't think that solves the problem. – Reactgular Jan 30 '14 at 21:58
  • 4
    He's not just traversing the graph performing independent operations like a search, he's aggregating the data from the child nodes. Flattening the tree destroys the structure information he needs in order to perform the aggregation. – Karl Bielefeldt Jan 30 '14 at 22:22
  • 1
    FYI I think this is the correct answer most people googling this question are looking for. +1 – Anders Arpi Jan 19 '15 at 9:24
4

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.

  • I just made a quick test. On my machine I could make make 14000 recursive calls before reaching stackoverflow. If the tree is balanced only 32 calls is needed to store 4 billion nodes. If each node is 1 byte(which it wont be) It would take 4 GB of ram to store a balanced tree of height 32. – Esben Skov Pedersen Aug 22 '15 at 19:20
  • I we were to use all 14000 calls in the stack. The tree would take up 2.6x10^4214 bytes if each node is one byte(which it wont be) – Esben Skov Pedersen Aug 22 '15 at 19:23
-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.

  • 2
    This is simply false. It is most certainly possible to traverse a tree without using recursion. It's not even hard. You can also do so more efficiently, quite trivially, as you can only include as much information in the explicit stack as you're sure you need for your specific traversal, whereas using recursion you end up storing more information than you actually need in many cases. – Servy Jan 30 '14 at 21:46
  • 2
    This controversy comes up every once in a while here. Some posters consider rolling your own stack not to be recursion, while others point out that they are just doing the same thing explicitly that the runtime would otherwise do implicitly. There is no point in arguing about definitions like this. – Kilian Foth Jan 30 '14 at 21:51
  • How do you define recursion then? I would define it as a function that invokes itself within its own definition. You can most certainly traverse a tree without ever doing that, as I have demonstrated in my answer. – Servy Jan 30 '14 at 21:53
  • 2
    Am I evil for enjoying the act of clicking the downvote on someone with such a high rep score? It's such a rare pleasure on this website. – Reactgular Jan 30 '14 at 21:54
  • 2
    Come on @Mat, that's kid stuff. You may disagree, like if you are afraid of bombing out on a tree that's too deep, that's a reasonable concern. You can just say so. – Mike Dunlavey Jan 30 '14 at 22:01

protected by gnat Aug 25 '15 at 0:10

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.