How can you order a hierarchy of objects by depth-level using LINQ?

Question

Consider this hierarchy

                     A
                     |
        --------------------------
        |                        |
        B                        C
        |                        |
--------|--------            ---------
|       |       |            |       |
D       E       F            G       H
|       |                    |       |
|   ---------             -------    |
|   |       |             |     |    |
I   J       K             L     M    N

Every object has a Parent property and an Items collection for the choldren, so for instance, E has a parent of B, N of H, etc. A has a value of null for the parent. B.Items contains D-F, etc.

What is a LINQ statement that I can sort these by their level? I don't care about the sort order within a level (i.e. the order of D-H doesn't matter, but they have to come after B and C which have to come after A.

Only way I can think is two separate linq statements:

1. Run an aggregate over this, calculating and storing the levels as you go
2. Run a second LINQ query over the results ordering by Level.

B is easy of course. It's A that I'm struggling with. I can do it procedurally of course, but I have to think this can be reduced to a LINQ statement.

Answer 1

You didn't specify what's the target of your query, so there are multiple correct answers:

1. LINQ to SQL or LINQ to Entities - support for recursive queries doesn't exist, so you'd either had to load the data into memory and perform LINQ to Objects query, or use a Stored Procedure in the database (most likely using Common Table Expression). You could also prepare a VIEW in the database and map it to your EF model.

2. LINQ to Objects is better suited to the job, but IMO you're still best with a simple method that calculated depth:

   public static int GetDepth(Item item)
   {
       int d = 0;
       while ((item = item.Parent) != null)
           d++;
       return d;
   }
   

   and the query is super simple later on

   var results = from item in data
                 let depth = GetDepth(item)
                 orderby depth descending
                 select item;
   

   It would be easy to write just one LINQ to Objects query if your data structure was different, and Parent had links to all the children. In that case querying the data is easier, because each item has a collection of dependant items, and LINQ works well with collections, in oposite to single items, like your Parent property. I wrote a blogpost about querying hierarchy of objects using LINQ a while ago, you might find it interesting.

Answer 2

Although my friends have posted some good answers, I'm wiling to provide another answer. If it's feasible to change the node structure for better performance you can set the depth property for every node once and then sort them based on the depth property.

public class Node
{
    public Node()
    {
        this.Items = new List<Node>();
        this.Parent = null;
        this.Depth = 0;
    }
    public Node Parent { get; set; }
    public List<Node> Items { get; set; }
    public int Depth { get; set; }
}

public void SetDepths(Node node, int depth)
{
    node.Depth = depth;
    foreach (var child in node.Items)
        SetDepths(child, depth + 1);
}
public void Sort(List<Node> nodes)
{
    SetDepths(nodes.Single(x => x.Parent == null), 1);
    nodes = nodes.OrderBy(x => x.Depth).ToList();
}

The recursive function should be called like :

SetDepths(rootNode, 1);

which here it's called in the sort method or you van choose any other places to do that.