Creating a tree from Parent/Child relation represented in a flat table

Question

I have a C# List of following fields which are returned by a stored procedure:

CarrierId   ParentCarrierId Name Descrition
1            NULL            A         AA
2              1             B         BB
3              1             C         CC
4              3             D         DD
5            NULL            E         EE

I need to construct a nested object list out of this output

So each object of Carrier should have list of all it's children. Can anyone help me construct a LINQ code to accomplish this?

Desired Result:

  CarrierId = 1
      |__________________ CarrierId = 2
      |
      |__________________ CarrierId = 3
      |
      |                        |___________________ CarrierId = 4
CarrierId = 5

Desired result should be as mentioned above

the following code arrange things in tree but a child still appears in the list

c.Children = carrierList.Where(child => child.ParentCarrierId == c.CarrierId).ToList();



 CarrierId = 1
      |
      |__________________ CarrierId = 2
      |
      |__________________ CarrierId = 3
      |                        |___________________ CarrierId = 4
      |

 CarrierId = 2

      |
 CarrierId = 3

      |
 CarrierId = 4

      |
 CarrierId = 5

I don't want this behavior. If something appeared as Child it should be removed from root.

Answer 1

This is what you need.

First, start with the source data:

var source = new []
{
    new { CarrierId = 1, ParentCarrierId = (int?)null, Name = "A", Description = "AA", },
    new { CarrierId = 2, ParentCarrierId = (int?)1, Name = "B", Description = "BB", },
    new { CarrierId = 3, ParentCarrierId = (int?)1, Name = "C", Description = "CC", },
    new { CarrierId = 4, ParentCarrierId = (int?)3, Name = "D", Description = "DD", },
    new { CarrierId = 5, ParentCarrierId = (int?)null, Name = "E", Description = "EE", },
};

Then, create a lookup by ParentCarrierId:

var lookup = source.ToLookup(x => x.ParentCarrierId);

Now we need an output structure:

public class Carrier
{
    public int Id;
    public List<Carrier> Children = new List<Carrier>();
    public string Name;
    public string Description;
}

Then, a build function to pop all of the carriers out by ParentCarrierId:

Func<int?, List<Carrier>> build = null;
build = pid =>
    lookup[pid]
        .Select(x => new Carrier()
        {
            Id = x.CarrierId,
            Name = x.Name,
            Description = x.Description,
            Children = build(x.CarrierId),
        })
        .ToList();

NB: It's recursive so it needs to be defined with the initial = null.

Finally we build:

List<Carrier> trees = build(null);

This gives: