Get All Children to One List - Recursive C#

Question

C# | .NET 4.5 | Entity Framework 5

I have a class in Entity Framework that looks like this:

public class Location
{
   public long ID {get;set;}
   public long ParentID {get;set;}
   public List<Location> Children {get;set;}
}

ID is the identifier of the location, ParentID links it to a parent, and Children contains all of the children locations of the parent location. I'm looking for some easy way, likely recursively, to get all "Location" and their children to one single List containing the Location.ID's. I'm having trouble conceptualizing this recursively. Any help is appreciated.

This is what I have so far, its an extension to the entity class, but I believe it could be done better/simpler:

public List<Location> GetAllDescendants()
{
    List<Location> returnList = new List<Location>();
    List<Location> result = new List<Location>();
    result.AddRange(GetAllDescendants(this, returnList));
    return result;
}

public List<Location> GetAllDescendants(Location oID, ICollection<Location> list)
{
    list.Add(oID);
    foreach (Location o in oID.Children)
    {
            if (o.ID != oID.ID)
                    GetAllDescendants(o, list);
    }
    return list.ToList();
}

UPDATED

I ended up writing the recursion in SQL, throwing that in a SP, and then pulling that into Entity. Seemed cleaner and easier to me than using Linq, and judging by the comments Linq and Entity don't seem the best route to go. Thanks for all of the help!

Answer 1

You can do SelectMany

List<Location> result = myLocationList.SelectMany(x => x.Children).ToList();

You can use where condition for some selective results like

List<Location> result = myLocationList.Where(y => y.ParentID == someValue)
                                      .SelectMany(x => x.Children).ToList();

If you only required Id's of Children you can do

List<long> idResult = myLocationList.SelectMany(x => x.Children)
                                    .SelectMany(x => x.ID).ToList();

Answer 2

This will do the trick:

class Extensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        var result = source.SelectMany(selector);
        if (!result.Any())
        {
            return result;
        }
        return result.Concat(result.SelectManyRecursive(selector));
    }
}

Use it like this:

List<Location> locations = new List<Location>();
//
// your code here to get locations
//
List<string> IDs = locations.SelectManyRecursive(l => l.Children).Select(l => l.ID).ToList();

Answer 3

Try this Extension method:

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    return source.SelectMany(x => (recursion(x) != null && recursion(x).Any()) ? recursion(x).Flatten(recursion) : null)
                 .Where(x => x != null);
}

And you can use it like this:

locationList.Flatten(x => x.Children).Select(x => x.ID);

Answer 4

I had no Children prop in my model, so Nikhil Agrawal's answer doesn't work for me, so here is my solution.

With following model:

public class Foo
{
    public int Id { get; set; }
    public int? ParentId { get; set; }  
    // other props
}

You can get children of one item using:

List<Foo> GetChildren(List<Foo> foos, int id)
{
    return foos
        .Where(x => x.ParentId == id)
        .Union(foos.Where(x => x.ParentId == id)
            .SelectMany(y => GetChildren(foos, y.Id))
        ).ToList();
}

For ex.

List<Foo> foos = new List<Foo>();

foos.Add(new Foo { Id = 1 });
foos.Add(new Foo { Id = 2, ParentId = 1 });
foos.Add(new Foo { Id = 3, ParentId = 2 });
foos.Add(new Foo { Id = 4 });

GetChild(foos, 1).Dump(); // will give you 2 and 3 (ids)

Answer 5

I would like to contribute my own solution, which was modified from the references below:

public static IEnumerable<T> Flatten<T, R>(this IEnumerable<T> source, Func<T, R> recursion) where R : IEnumerable<T>
{
    var flattened = source.ToList();

    var children = source.Select(recursion);

    if (children != null)
    {
        foreach (var child in children)
        {
            flattened.AddRange(child.Flatten(recursion));
        }
    }

    return flattened;
}

Example:

var n = new List<FamilyMember>()
{
    new FamilyMember { Name = "Dominic", Children = new List<FamilyMember>() 
        {
            new FamilyMember { Name = "Brittany", Children = new List<FamilyMember>() }
        }
    }
}.Flatten(x => x.Children).Select(x => x.Name);

Output:

• Dominic
• Brittany

Class:

public class FamilyMember {
    public string Name {get; set;}
    public List<FamilyMember> Children { get; set;}
}

Ref. https://stackoverflow.com/a/21054096/1477388

Note: Can't find the other reference, but someone else on SO published an answer that I copied some code from.

Answer 6

Entity framework does not currently support recursion, and for that reason you can either

• Rely on lazy loading child collections as you have done (beware the N+1 problem)
• Query an arbitrary depth of objects (This will be an ugly query, though you could generate it using System.Linq.Expressions)

The only real option would be to avoid using LINQ to express the query, and instead resort to standard SQL.

Entity framework supports this scenario fairly well whether you're using code first or not.

For code-first, consider something along the lines of

var results = this.db.Database.SqlQuery<ResultType>(rawSqlQuery)

For model-first, consider using a defining query which I think is a good option as it allows further composition, or stored procedures.

To recursively get back data, you will need to understand recursive CTEs assuming you're using SQL Server, and that it is version 2005+

EDIT:

Here is the code for a recursive query to an arbitrary depth. I put this together just for fun, I doubt it would be very efficient!

var maxDepth = 5;

var query = context.Locations.Where(o => o.ID == 1);
var nextLevelQuery = query;

for (var i = 0; i < maxDepth; i++)
{
    nextLevelQuery = nextLevelQuery.SelectMany(o => o.Children);
    query = query.Concat(nextLevelQuery);
}

The flattened list is in the variable query

Answer 7

The accepted answer from @NikhilAgrawal will not recursively get all children and grandchildren as @electricalbah has pointed out.

I do miss the answer from @EricLippert that was given on Code Review.

https://codereview.stackexchange.com/a/5661/96658

static IEnumerable<T> DepthFirstTreeTraversal<T>(T root, Func<T, IEnumerable<T>> children)      
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        // If you don't care about maintaining child order then remove the Reverse.
        foreach(var child in children(current).Reverse())
            stack.Push(child);
        yield return current;
    }
}

Called like this:

static List<Location> AllChildren(Location start)
{
    return DepthFirstTreeTraversal(start, c=>c.Children).ToList();
}

I made an example below with SelectMany. As you can see from Immediate Window you will not even get the Parent Id if you use that solution.

Answer 8

Create list to add all child using recursively public static List list = new List();

recursive funtion

 static  void GetChild(int id) // Pass parent Id
                {

                    using (var ctx =  new CodingPracticeDataSourceEntities())
                    {
                        if (ctx.Trees.Any(x => x.ParentId == id))
                        {
                            var childList = ctx.Trees.Where(x => x.ParentId == id).ToList();
                            list.AddRange(childList);
                            foreach (var item in childList)
                            {
                                GetChild(item.Id);
                            }

                        }

                    }
                }

Sample model

 public partial class Tree
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public Nullable<int> ParentId { get; set; }
    }

Answer 9

Assuming Locations is a DbSet<Location> in your DB context, this will solve your problem "I'm looking for some easy way ... to get all 'Location' and their children to one single List containing the Location.ID's". Seems like I'm missing something, so please clarify if so.

dbContext.Locations.ToList()
// IDs only would be dbContext.Locations.Select( l => l.ID ).ToList()

Answer 10

This is my method for Flattening the children.

private Comment FlattenChildComments(Comment comment, ref Comment tempComment)
    {
        if (comment.ChildComments != null && comment.ChildComments.Any())
        { 
            foreach (var childComment in comment.ChildComments)
            {
                tempComment.ChildComments.Add(childComment);
                FlattenChildComments(childComment, ref tempComment);
            }
        }
        comment.ChildComments = tempComment.ChildComments;
        return comment;
    }

Answer 11

For the people who needs something generic:

/// <summary>
/// Recursively enumerate all children, grandchildren etc... in a 1-dimentional IEnumerable
/// </summary>
/// <typeparam name="TModel">The type of the model</typeparam>
/// <param name="root">The root from which to enumerate children</param>
/// <param name="childSelector">The selector on how to select the children of the root.</param>
/// <returns>A 1-dimentional IEnumerable of all it's children, grandchildren etc.. recursively.</returns>
public static IEnumerable<TModel> EnumerateChildren<TModel>(TModel root, Func<TModel, IEnumerable<TModel>> childSelector)
{
    var children = childSelector.Invoke(root);
    if (children == null)
    {
        yield break;
    }

    foreach (var child in children)
    {
        yield return child;

        foreach (var grandChild in EnumerateChildren(child, childSelector))
        {
            yield return grandChild;
        }
    }
}

Usage:

var location = GetLocation(); // Get your root.

var children = EnumerateChildren(location, l => l.Children);