Traverse a hierarchical structure with LINQ-to-Hierarchical

Originally published on blog.einbu.no July 13. 2009

RecentIy I needed to find a specific TreeNode in a TreeView control. I expected that would be easy with LINQ, but quickly realized that there is no method in the .NET framework that will let me traverse all nodes of a hierarchy. I decided to create one myself.

I started by trying out how I would expect to use it. I quickly landed on a syntax like this:

var q = from node in root.FlattenHierarchy()
        select node;

How would the hierarchy be flattened? Well, implemented as an extension method, the method would look like this:

public static class LinqToHierarchical
{
    public static IEnumerable FlattenHierarchy(this TreeNode node)
    {
        yield return node;
        if(node.Nodes != null)
        {
            foreach(var child in node.Nodes)
            {
                foreach(var childOrDescendant in child.FlattenHierarchy())
                {
                    yield return childOrDescendant;
                }
            }
        }
    }
}

The above code works, and there are no problems with it if you know beforehand what kind of hierarchy you're going to work with. In the code above, it works well with the nodes of a Windows Forms TreeView control.

Yet still, I'm not satisfied. Can I make a generic extension method that will flatten any hierarchy? Even those not made up of TreeNode objects?

To do that, we need to analyze which parts of the method needs to be swapped out. That would be the TreeNode's Nodes property. Can we acccess that in an other way? Yes, I think a delegate can help us, so lets give it a try:

public static IEnumerable FlattenHierarchy(this T node, Func getChildEnumerator)
{
    yield return node;
    if(getChildEnumerator(node) != null)
    {
        foreach(var child in getChildEnumerator(node))
        {
            foreach(var childOrDescendant in child.FlattenHierarchy(getChildEnumerator))
            {
                yield return childOrDescendant;
            }
        }
    }
}

Now, that wasn't difficult. But did we just complicate the usage of our extension method? Yes, we did. When we're going to flatten a hierarchy, we'll have to tell where to find the children. Not to hard though, since we can use a lambda expression for that. Here's how we use it now:

var q = from node in root.FlattenHierarchy(x => x.Nodes)
        select node;

Now we're able to use it with any hierarchy. Some samples include:

//The filesystem
var q = from directory in new DirectoryInfo(@"c:\").FlattenHierarchy(x => x.GetDirectories())
        select directory;

//XML (Yeah, I know: xml.Descendants() will also flatten this...)
var xml = XElement.Load(@"filename.xml");
var q = from element in xml.FlattenHierarchy(x => x.Elements())
        select element;

//Control tree in Windows Forms or in ASP.NET
var q = from control in Controls.FlattenHierarchy(x => x.Controls)
        select control;

Now, where can you go from here? I think what we have here is quite usefull as is, but some ideas include;

Limit traversal on depth level
Include leaf nodes of types that don't include a subnode collection
Traverse one level at a time, instead of traversing down each branch as we find them