Let us define a basic abstraction of a tree element
In a nutshell that's all you need. A tree node is a structure where each element has children that can be iterated over, and the hierarchy of all the elements defines the tree structure. This is of course a generalization, as we could put additional constraints such as each element being only available once in the tree, but I'll leave it up to the developer to enforce such constraints. I'm merely trying to iterate over the tree nodes.
With that in mind, we can define a function that maps
There are two common ways to do recursion: function recursion where a function points to itself, or stack-based recursion where we use a stack to keep a list of evaluation arguments on a stack and evaluate them as need be. We'll use stack-based iteration because it tends to be more scalable.
Without further ado let’s get to the meat of the code:
Let’s look at what the code does. It first creates a stack to hold the objects that need to be evaluated. It then pushes the root item onto the stack. The loop is quite simple. While the stack has items in it, first pop an item off the stack, yield it using the c# iterator pattern, then call childrenMappingFunction to get the children (IEnumerable<T>) from T item. Then, for each child in children, add the child to the stack, so that it is evaluated on the next iteration of the while loop. That’s pretty much it. Because of the elegance of c# iterators, it’s easy to use this function to map a tree to a flatter IEnumerable<T> without ever having to concern ourselves with the details again.
I’ve added some additional overloads and parameters to allow customizing how we get the data back. The only one that might need a bit of explanation is leftToRight. What I discovered when first using this class is that because of the way items are added to the stack, the elements returned from the function are not necessarily in the same order that they were in each nodes IEnumerable. This is not always a problem, but certainly can be in certain use cases so I added a modifier, leftToRight, that ensures that the data is added to the stack in reverse order, so that when it is popped off the stack, it’s in the order that the elements were returned from IEnumerable. It’s not the most efficient way to do this and I recognize that, but I don’t use that option most of the time and in the cases where I did use it performance was not a major concern. If anyone wants to provide a cleaner implementation I welcome feedback. Here is the class in it’s entirety:
Let’s look at a use case:
Given a .Net Winforms TreeView, find all nodes in the entire tree that start with E.
Because Node.Nodes does not implement IEnumerable<Node> we need a helper function, so we’ll use that with the deep enumerator.
For a second example let us define a slightly cleaner interface:
What if we wanted to find all nodes in List<ITextNode> nodes where one or more of the children (root included) start with the letter E.
Using LINQ this is pretty straightforward:
These are just a few examples. I hope you find this class useful. Deep tree enumeration is something I find myself doing fairly often, and this class has eliminated a lot of redundant code for me.