How can I sort a list of entries (Id, ParentId) into a tree hierarchy? [Answered]

I have an unsorted list of entries with two notable fields: Id and ParentId. I would like to sort this data in such a way that if an item has a non-null ParentId, it ends up underneath the parent item with the corresponding Id. The ordering of items at a particular level (e.g. the direct children of a parent) has to be increasing.

The ordering or "root" items (ParentId == null) also has to be increasing. Both Id and ParentId are of type int?. The data hierarchy can be any number of levels deep.

I've tried every LINQ solution from StackOverflow, including a custom one that uses a for loop:

var categories = woo.Category.Enumerate().OrderBy(c => c.id).ToList(); // Source data
var ordered = new ObservableCollection<ProductCategory>(categories);

for (int i = 0; i < ordered.Count; i++)
{
    var category = ordered[i];
    if (category.parent is null or 0)
        ordered.Move(i, 0); // Move root item to the top, shift everything down
    else if (ordered.FirstOrDefault(o => o.id == category.parent) is { } parent && ordered.IndexOf(parent) is { } parentIndex and > 0)
        ordered.Move(i, parentIndex + 1); // Move item under its parent, shift everything down
}

but nothing gives the desired result.

I only have to do this once to sort a dataset, so performance and efficiency do not matter at all.

Sounds like you should build the tree, then go through and add to the list based on the location in the tree

I was hoping that there would be a simpler solution, but I will try it. Thanks!

Why not build an actual tree instead of trying to sort it into some flat list?
Building the tree is not too complicated. Then you can build a flat list from it if you really need to. But you can also display it as a hierarchy via TreeView.

Okay, this was the correct solution and it was easier than I was expecting. Thanks for everyone for the help!

✅ This post has been marked as answered!