Recursive non-binary, non-sorted tree search using c# lambas

Question

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


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

1) How would you write the recursive lambda expression to return the TreeNode with a particular value (or null if not found) assuming the values are unique? Of course #1 can be answered using #2, but I imagine there might be a more efficient way if you know there are no duplicates.

2) Assuming values are not unique and now returning a List of matches instead?

Answer 1

Edit: Corrected the code, I did in fact compile and test both pieces of code, but I must've pasted in versions before I fixed them in VS. Sorry about that.

I've added a Subversion repository with the code, including unit tests, to ensure it now works as expected, is here, log in with username and password both as 'guest', without the quotes.

---

Like this:

1: Find first

Func<TreeNode, String, TreeNode> findNode = null; // satisfy recursion re-use
findNode = (n, value) =>
{
    if (n == null) return n;
    if (n.Value == value) return n;
    foreach (var subNode in n.Nodes)
    {
        TreeNode foundNode = findNode(subNode, value);
        if (foundNode != null) return foundNode;
    }
    return null;
};

Note that the trap here is that for a lambda or a delegate to be recursive, you need to declare the variable first, with a known value, before you assign the actual delegate to it. Otherwise the compiler will complain that you're using a variable before it has been given a value.

2: Find all

Func<TreeNode, String, List<TreeNode>> findNodes = null;
findNodes = (n, value) =>
{
    var result = new List<TreeNode>();
    if (n == null) return result;
    if (n.Value == value) result.Add(n);
    foreach (var subNode in n.Nodes)
    {
        result.AddRange(findNodes(subNode, value));
    }
    return result;
};

The trick is here to just gather up the nodes on each level, and aggregate upwards.

Answer 2

How about this..

public class Node<T> where T:IComparable
{
    public T Value { get; set; }

    public IList<Node<T>> Children { get; set; }

    public override string ToString()
    {
        return Value.ToString();
    }

    public static Func<T, Node<T>, Node<T>> GetFindFirstFunc()
    {
        Func<T, Node<T>,Node<T>> func = null;
        func = (value,currentNode) =>
            {
                if (currentNode.Value.CompareTo(value) == 0)
                {
                    return currentNode;
                }
                if (currentNode.Children != null)
                {
                    foreach (var child in currentNode.Children)
                    {                            
                        var result = func(value, child);
                        if (result != null)
                        {
                            //found the first match, pass that out as the return value as the call stack unwinds
                            return result;
                        }
                    }
                }
                return null;
            };
        return func;
    }

    public static Func<T, Node<T>, IEnumerable<Node<T>>> GetFindAllFunc()
    {
        Func<T, Node<T>, IEnumerable<Node<T>>> func = null;
        List<Node<T>> matches = new List<Node<T>>();
        func = (value, currentNode) =>
        {
            //capture the matches  List<Node<T>> in a closure so that we don't re-create it recursively every time.
            if (currentNode.Value.CompareTo(value) == 0)
            {
                matches.Add(currentNode);
            }
            if (currentNode.Children != null)
            {
                //process all nodes
                foreach (var child in currentNode.Children)
                {
                    func(value, child);
                }
            }
            return matches;
        };
        return func;
    }       
}

Here is the calling code:

static void Main(string[] args)
    {
        Node<int> rootNode = new Node<int>
        {
            Value = 1,
            Children = new List<Node<int>>
             {
                 new Node<int>
                 {  Value = 2,
                                 Children = new List<Node<int>>
                                 {
                                     new Node<int>{ Value = 7},
                                     new Node<int>{ Value = 4}                                                            
                                 }
                 },
                 new Node<int>
                 {  Value = 5,
                                 Children = new List<Node<int>>
                                 {
                                     new Node<int>{ Value = 6},
                                     new Node<int>{ Value = 7}                                                            
                                 }
                 }
             }
        };


        Func<int, Node<int>, Node<int>> findFirst = Node<int>.GetFindFirstFunc();
        var firstValue = findFirst(7, rootNode);           



        Func<int, Node<int>, IEnumerable<Node<int>>> findAll = Node<int>.GetFindAllFunc();
        var allvalues = findAll(7, rootNode);           
    }