# How do I traverse a tree without using recursion?

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?

• 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 Jan 30, 2014 at 21:13
• I also found a lot of help at this Google Search, specifically Morris Traversal. Jan 30, 2014 at 21:17
• @RobertHarvey thanks Rob, I wasn't sure what terms this would go under. Jan 30, 2014 at 21:19
• 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. Jan 30, 2014 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. Jan 30, 2014 at 21:47

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? Jan 30, 2014 at 21:56
• @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. Jan 30, 2014 at 21:56
• I don't think that solves the problem. Jan 30, 2014 at 21:58
• 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. Jan 30, 2014 at 22:22
• FYI I think this is the correct answer most people googling this question are looking for. +1 Jan 19, 2015 at 9:24

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. Aug 22, 2015 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) Aug 22, 2015 at 19:23

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.

• 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. Jan 30, 2014 at 21:46
• 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. Jan 30, 2014 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. Jan 30, 2014 at 21:53
• 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. Jan 30, 2014 at 21:54
• 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. Jan 30, 2014 at 22:01