Sort Items by parent relationship

Question

Coming from here I ask myself if there is a easier way to sort a class like

public class ParentChild
{
    int ID { get; set; }
    int ParentID { get; set; }

    public ParentChild(int id, int pid)
    {
        ID = id;
        ParentID = pid;
    }
}

depending on it's parent-relationship.

e.g.

List<ParentChild> pcItems = new List<ParentChild>()
{           
    new ParentChild(1,0), // 0 is the default value in case of no parent
    new ParentChild(2,1),
    new ParentChild(3,2),
    new ParentChild(4,2),
    new ParentChild(5,1),
    new ParentChild(6,4),
    new ParentChild(7,1),
    new ParentChild(8,6),
    new ParentChild(9,3)
};

So the Items should have the following sort order: sorted first by child-relation and then by the ID.

1       // root
+-2
| +-3
| | +-9 // is the child of 3
| | 4   //is the 2nd child of 2 and has the higher ID conmpared to 3
| | +-6
| |   +-8
| 5
7

This question is not about to display data in hierarchical order. It's just about a simpler / not recursive / linq OrderBy / Sort compared to my answer in the linked post.

Answer 1

Once you fix the constructor in ParentChild you should find that this works:

var lookup = pcItems.ToLookup(x => x.ParentID, x => x.ID);

Func<int, int, IEnumerable<string>> build = null;
build = (pid, level) =>
    lookup[pid]
        .SelectMany(id =>
            new [] { "".PadLeft(level * 4) + id.ToString() }
            .Concat(build(id, level + 1)));

IEnumerable<string> results = build(0, 0);

That gives you this:

It is recursive, but at least it is three lines of code. ;-)

---

To get just a sorted result:

var lookup = pcItems.ToLookup(x => x.ParentID, x => x.ID);
Func<int, int, IEnumerable<ParentChild>> build = null;
build = (pid, level) => lookup[pid]
                        .SelectMany(id => new[] { pcItems.Single(x => x.ID == id) }
                        .Concat(build(id, level + 1)));
IEnumerable<ParentChild> results = build(0, 0);

---

A slightly cleaner version:

var lookup = pcItems.ToLookup(x => x.ParentID);

Func<int, int, IEnumerable<ParentChild>> build = null;
build = (pid, level) =>
    lookup[pid].SelectMany(pc => new[] { pc }.Concat(build(pc.ID, level + 1)));

IEnumerable<ParentChild> results = build(0, 0);