Recursive lambda expression to traverse a tree in C#

Question

Can someone show me how to implement a recursive lambda expression to traverse a tree structure in C#.

Solution 1

Ok, I found some free time finally.
Here we go:

class TreeNode
{
    public string Value { get; set;}
    public List<TreeNode> Nodes { get; set;}


    public TreeNode()
    {
        Nodes = new List<TreeNode>();
    }
}

Action<TreeNode> traverse = null;

traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};

var root = new TreeNode { Value = "Root" };
root.Nodes.Add(new TreeNode { Value = "ChildA"} );
root.Nodes[0].Nodes.Add(new TreeNode { Value = "ChildA1" });
root.Nodes[0].Nodes.Add(new TreeNode { Value = "ChildA2" });
root.Nodes.Add(new TreeNode { Value = "ChildB"} );
root.Nodes[1].Nodes.Add(new TreeNode { Value = "ChildB1" });
root.Nodes[1].Nodes.Add(new TreeNode { Value = "ChildB2" });

traverse(root);

Solution 2

A proper solution, and indeed the idiomatic solution in many functional programming languages, would be the use of a fixed-point combinator. In a nutshell: a fixed-point combinator answers the question “how do I define an anonymous function to be recursive?”. But the solution is so nontrivial that whole articles are written to explain them.

A simple, pragmatic alternative is to “go back in time” to the antics of C: declaration before definition. Try the following (the “factorial” function):

Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

Works like a charm.

Or, for a pre-order tree traversal on an object of class TreeNode which implements IEnumerable<TreeNode> appropriately to go over its children:

Action<TreeNode, Action<TreeNode>> preorderTraverse = null;
preorderTraverse = (node, action) => {
    action(node);
    foreach (var child in node) preorderTraverse(child, action);
};

Solution 3

A simple alternative is to “go back in time” to the antics of C and C++: declaration before definition. Try the following:

Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

Works like a charm.

Yes, that does work, with one little caveat. C# has mutable references. So make sure you don't accidentally do something like this:

Func<int, int> fact = null;
fact = x => (x == 0) ? 1 : x * fact(x - 1);

// Make a new reference to the factorial function
Func<int, int> myFact = fact;

// Use the new reference to calculate the factorial of 4
myFact(4); // returns 24

// Modify the old reference
fact = x => x;

// Again, use the new reference to calculate
myFact(4); // returns 12

Of course, this example is a bit contrived, but this could happen when using mutable references. If you use the combinators from aku's links, this won't be possible.

Solution 4

Assuming a mythical object TreeItem, that conatins a Children collection to represent your hierarchy.

    public void HandleTreeItems(Action<TreeItem> item, TreeItem parent)
    {
        if (parent.Children.Count > 0)
        {
            foreach (TreeItem ti in parent.Children)
            {
                HandleTreeItems(item, ti);
            }
        }

        item(parent);
    }

Now to call it, passing in the lambda that handles one item, by printing its name to the console.

HandleTreeItems(item => { Console.WriteLine(item.Name); }, TreeItemRoot);

View more solutions

Comments

[aku]

Out of curiosity, how this factorial function can help to answer on given question?

[LarryB]

IIRC the ForEach extension method doesn't exist in the Framework, so you have to write it yourself (which is an easy task).

[Guillaume86]

because it's recursive

[ICTMitchell]

HandleTreeItems is not a lambda, it just takes a lambda as argument. Thus this does not answer the specific question.

[Alexandre]

It's easier for other users to understand the solution if it's in a commonly considered recursive function than it would be having to understand OP's specific problem.