Functionally traversing a tree in C#

Question

Consider the following extension method in c#, Traverse:

IEnumerable<T> Traverse<T>( this IEnumerable<T> source, 
                              Func<T, IEnumerable<T>> fnRecurse );

This method allows one to recurse through a tree as defined by T and whatever function causes T to return its subnodes.

Now consider the following implementation of T:

class Node
{
  public string Name;
  public List<Node> Children;
}

My goal is to write the shortest function possible that will return an IEnumerable containing the fully qualified paths for every node in this tree. Something like:

var node = GetParentNode();
return node.Traverse( node => node.Children )
           .Select( node => GetParentName(node) + ":" + node.Name );

Obviously, adding a Parent property to Node makes the problem trivial. Instead I'd like to build my parent strings inside a functor somehow. I don't think this would be too hard in C++ but I don't see how to do it in C#. Any ideas?

Answer 1

I think the trick is to simply not pass down a Node type. Instead pass down the Node and it's qualified path. For example

var node = GetTheStartNode();
var start = new { Path = node.Name; Node = node };
var paths = 
   start
     .Traverse( x => x.Node.Children.Select(
        c => new { .Path = x.Path + ":" c.Name; .Node=c) )
     .Select(x => x.Path);

Answer 2

Well I don't think you can avoid searching the tree until you find the node you're looking for without storing a parent pointer.

You'll start from the root. Test the current node for a match. If it is a match, return the node or just the name (as a list of this one element). Otherwise, if this is a leaf node, return null. If not a leaf, traverse it's children and if the children return non-null value, prepend the current node to your list and return that.

Returning from the original call, null means no match found. Otherwise you'll have your list of nodes in order.

Answer 3

Clearest and most reusable solution:

Create a generic method that enumerates all possible pathes:

static IEnumerable<IEnumerable<T>> ComputePaths<T>(T Root, Func<T, IEnumerable<T>> Children) {
    yield return new[] { Root };
    foreach (var Child in Children(Root)) 
        foreach (var ChildPath in ComputePaths(Child, Children)) 
            yield return new[] { Root }.Concat(ChildPath);            
}

The resulting enumeration can be easily transformed into your string representation.

    // All paths
    var Paths = ComputePaths(Test, x => x.Children);

    // Compute string representation 
    var StrPaths = from p in Paths select string.Join(":", p.Select(t => t.Name).ToArray());

    foreach(var p in StrPaths)
        Console.WriteLine(p);