Recursive Hierarchy - Recursive Query using Linq

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?

Answer 1

The simplest solution seems to introduce a recursive method. You can't get recursive just by LINQ itself:

IEnumerable<X> GetChildren(X x)
{
    foreach (var rChild in x.Children.SelectMany(child => GetChildren(child)))
    {
        yield return rChild;
    }
}

If you have lazy loading, then this should work:

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

Answer 2

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

Answer 3

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

Answer 4

I like more the linq way to do recursive.

public static IEnumerable<TReturn> Recursive<TItem, TReturn>(this TItem item, Func<TItem, IEnumerable<TReturn>> select, Func<TItem, IEnumerable<TItem>> recurrence)
    {
        return select(item).Union(recurrence(item).Recursive(select, recurrence));
    }