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

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);