Creating a tree with LINQ expression

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

Answer 1

First create a lookup that maps a parent ID to its children:

var lookup = carriers.ToLookup(carrier => carrier.ParentCarrierId);

The go through each node and assign its children based on the lookup:

foreach(var carrier in carriers)
    carrier.Children = lookup[carrier.CarrierId];

To get all of the root nodes just get the null values from the lookup:

var roots = lookup[null];

Note that this entire operation is O(n), as building the lookup is O(n) and all of the children for every single carrier can be found in O(n) time, rather than taking O(n^2) time as in the other solutions posted (as they use an O(n) operation to find all of the children for a single node). This makes this code dramatically faster than the other options, in addition to being much simpler and shorter.