Recursive Hierarchy - Recursive Query using Linq

Question

Recursive Hierarchy - Recursive Query using Linq

c# entity-framework linq recursion

Question

I am using Entity Framework (version 6) to map to a recursive hierarchy and it maps nicely.

My issue is that I want to recursively get ALL child nodes of a particular node in the hierarchy.

I get the child nodes quite easily using Linq:

var recursiveList = db.ProcessHierarchyItems
            .Where(x => x.id == id)
            .SelectMany(x => x.Children);

Does anybody know of a clean implementation, that will recursively get all children?

Keith Doran

Popular Answer

Thanks Servy, I expanded on your code a bit to allow for iterating single items, as well as collections. I came across when looking for a way to find out if an exception or any inner exceptions were of a certain type, but this will have many uses.

Here is a fiddle with examples, test cases, etc. dotnetfiddle LinqTraversal

Just the helpers:

public static class LinqRecursiveHelper
{
    /// <summary>
    /// Return item and all children recursively.
    /// </summary>
    /// <typeparam name="T">Type of item.</typeparam>
    /// <param name="item">The item to be traversed.</param>
    /// <param name="childSelector">Child property selector.</param>
    /// <returns></returns>
    public static IEnumerable<T> Traverse<T>(this T item, Func<T, T> childSelector)
    {
        var stack = new Stack<T>(new T[] { item });

        while (stack.Any())
        {
            var next = stack.Pop();
            if (next != null)
            {
                yield return next;
                stack.Push(childSelector(next));
            }
        }
    }

    /// <summary>
    /// Return item and all children recursively.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="item"></param>
    /// <param name="childSelector"></param>
    /// <returns></returns>
    public static IEnumerable<T> Traverse<T>(this T item, Func<T, IEnumerable<T>> childSelector)
    {
        var stack = new Stack<T>(new T[] { item });

        while (stack.Any())
        {
            var next = stack.Pop();
            //if(next != null)
            //{
            yield return next;
            foreach (var child in childSelector(next))
            {
                stack.Push(child);
            }
            //}
        }
    }

    /// <summary>
    /// Return item and all children recursively.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="items"></param>
    /// <param name="childSelector"></param>
    /// <returns></returns>
    public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items,
      Func<T, IEnumerable<T>> childSelector)
    {
        var stack = new Stack<T>(items);
        while (stack.Any())
        {
            var next = stack.Pop();
            yield return next;
            foreach (var child in childSelector(next))
                stack.Push(child);
        }
    }
}

Duane McKinney

View more on Stack Overflow

Servy · Accepted Answer · 6/25/2015 3:08:44 PM

While it is possible to use a recursive method here, you can traverse this tree structure using an explicit stack instead to avoid using the stack space, which isn't always sufficient for large tree structures. Such a method is also very nice as an iterator block, and iterator blocks are much less expensive when recursive than regular methods, so this will perform better as well:

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items, 
    Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>(items);
    while(stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach(var child in childSelector(next))
            stack.Push(child);
    }
}

Recursive Hierarchy - Recursive Query using Linq

Question

Fastest Entity Framework Extensions

Accepted Answer

Popular Answer

Performance

Expression Evaluator

Related