How to search Hierarchical Data with Linq

Question

I need to search a tree for data that could be anywhere in the tree. How can this be done with linq?

class Program
{
    static void Main(string[] args) {

        var familyRoot = new Family() {Name = "FamilyRoot"};

        var familyB = new Family() {Name = "FamilyB"};
        familyRoot.Children.Add(familyB);

        var familyC = new Family() {Name = "FamilyC"};
        familyB.Children.Add(familyC);

        var familyD = new Family() {Name = "FamilyD"};
        familyC.Children.Add(familyD);

        //There can be from 1 to n levels of families.
        //Search all children, grandchildren, great grandchildren etc, for "FamilyD" and return the object.


    }
}

public class Family {
    public string Name { get; set; }
    List<Family> _children = new List<Family>();

    public List<Family> Children {
        get { return _children; }
    }
}

Answer 1

That's an extension to It'sNotALie.s answer.

public static class Linq
{
    public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector)
    {
        return selector(source).SelectMany(c => Flatten(c, selector))
                               .Concat(new[] { source });
    }
}

Sample test usage:

var result = familyRoot.Flatten(x => x.Children).FirstOrDefault(x => x.Name == "FamilyD");

Returns familyD object.

You can make it work on IEnumerable<T> source too:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
{
    return source.SelectMany(x => Flatten(x, selector))
        .Concat(source);
}

Answer 2

Another solution without recursion...

var result = FamilyToEnumerable(familyRoot)
                .Where(f => f.Name == "FamilyD");


IEnumerable<Family> FamilyToEnumerable(Family f)
{
    Stack<Family> stack = new Stack<Family>();
    stack.Push(f);
    while (stack.Count > 0)
    {
        var family =  stack.Pop();
        yield return family;
        foreach (var child in family.Children)
            stack.Push(child);
    }
}

Answer 3

Simple:

familyRoot.Flatten(f => f.Children);
//you can do whatever you want with that sequence there.
//for example you could use Where on it and find the specific families, etc.

IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector)
{
    return selector(source).SelectMany(c => Flatten(selector(c), selector))
                           .Concat(new[]{source});
}

Answer 4

So, the simplest option is to write a function that traverses your hierarchy and produces a single sequence. This then goes at the start of your LINQ operations, e.g.

    IEnumerable<T> Flatten<T>(this T source)
    {
      foreach(var item in source) {
        yield item;
        foreach(var child in Flatten(item.Children)
          yield child;
      }
    }

To call simply: familyRoot.Flatten().Where(n => n.Name == "Bob");

A slight alternative would give you a way to quickly ignore a whole branch:

    IEnumerable<T> Flatten<T>(this T source, Func<T, bool> predicate)
    {
      foreach(var item in source) {
         if (predicate(item)) {          
            yield item;
            foreach(var child in Flatten(item.Children)
               yield child;
      }
    }

Then you could do things like: family.Flatten(n => n.Children.Count > 2).Where(...)

Answer 5

I like Kenneth Bo Christensen's answer using stack, it works great, it is easy to read and it is fast (and doesn't use recursion). The only unpleasant thing is that it reverses the order of child items (because stack is FIFO). If sort order doesn't matter to you then it's ok. If it does, sorting can be achieved easily using selector(current).Reverse() in the foreach loop (the rest of the code is the same as in Kenneth's original post)...

public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector)
{            
    var stack = new Stack<T>();
    stack.Push(source);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var child in selector(current).Reverse())
            stack.Push(child);
    }
}

Answer 6

Well, I guess the way is to go with the technique of working with hierarchical structures:

1. You need an anchor to make

2. You need the recursion part

   // Anchor
   
   rootFamily.Children.ForEach(childFamily => 
   {
       if (childFamily.Name.Contains(search))
       {
          // Your logic here
          return;
       }
       SearchForChildren(childFamily);
   });
   
   // Recursion
   
   public void SearchForChildren(Family childFamily)
   {
       childFamily.Children.ForEach(_childFamily => 
       {
           if (_childFamily.Name.Contains(search))
           {
              // Your logic here
              return;
           }
           SearchForChildren(_childFamily);
       });
   }
   

Answer 7

I have tried two of the suggested codes and made the code a bit more clear:

    public static IEnumerable<T> Flatten1<T>(this T source, Func<T, IEnumerable<T>> selector)
    {
        return selector(source).SelectMany(c => Flatten1(c, selector)).Concat(new[] { source });
    }

    public static IEnumerable<T> Flatten2<T>(this T source, Func<T, IEnumerable<T>> selector)
    {            
        var stack = new Stack<T>();
        stack.Push(source);
        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current;
            foreach (var child in selector(current))
                stack.Push(child);
        }
    }

Flatten2() seems to be a little bit faster but its a close run.

Answer 8

Some further variants on the answers of It'sNotALie., MarcinJuraszek and DamienG.

First, the former two give a counterintuitive ordering. To get a nice tree-traversal ordering to the results, just invert the concatenation (put the "source" first).

Second, if you are working with an expensive source like EF, and you want to limit entire branches, Damien's suggestion that you inject the predicate is a good one and can still be done with Linq.

Finally, for an expensive source it may also be good to pre-select the fields of interest from each node with an injected selector.

Putting all these together:

public static IEnumerable<R> Flatten<T,R>(this T source, Func<T, IEnumerable<T>> children
    , Func<T, R> selector
    , Func<T, bool> branchpredicate = null
) {
    if (children == null) throw new ArgumentNullException("children");
    if (selector == null) throw new ArgumentNullException("selector");
    var pred = branchpredicate ?? (src => true);
    if (children(source) == null) return new[] { selector(source) };

    return new[] { selector(source) }
        .Concat(children(source)
        .Where(pred)
        .SelectMany(c => Flatten(c, children, selector, pred)));
}