66

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

0

4 Answers 4

82

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);
2
  • 1
    IIRC the ForEach extension method doesn't exist in the Framework, so you have to write it yourself (which is an easy task).
    – VVS
    Nov 26, 2010 at 18:14
  • ForEach is an existing instance method of List<T>. Oct 3, 2022 at 12:23
33

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);
};
3
  • 2
    Out of curiosity, how this factorial function can help to answer on given question?
    – aku
    Sep 14, 2008 at 10:46
  • 11
    because it's recursive Nov 11, 2013 at 12:10
  • 1
    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.
    – Alexandre
    Apr 10, 2019 at 13:44
18

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.

0
1

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);
1
  • 1
    HandleTreeItems is not a lambda, it just takes a lambda as argument. Thus this does not answer the specific question.
    – Macke
    Oct 17, 2016 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.