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

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 2

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