Efficient ordering of hierarchy data with only parentId

Question

Problem

What is the fastest method to order a flat unordered set of nodes such that the parent is always listed before it's children. My current solution uses a queue to iterate the tree in a breadth first manner. However I've been wondering if there was a better / more efficient method.

Notes:

I can't pre compute any values
Id and ParentId could also be Guids (even if ints I can't guarantee sequential ids)

Linq Pad Code

void Main()
{
    var nodes = new Node[] {
        new Node { Id = 7, ParentId = 3 },
        new Node { Id = 4, ParentId = 2 },
        new Node { Id = 1, ParentId = 0 },
        new Node { Id = 2, ParentId = 1 },
        new Node { Id = 3, ParentId = 1 },

        new Node { Id = 5, ParentId = 2 },
        new Node { Id = 6, ParentId = 3 },
        new Node { Id = 8, ParentId = 0 },
    };

    SortHierarchy(nodes).Dump();
}

IEnumerable<Node> SortHierarchy(IEnumerable<Node> list)
{
    // hashtable lookup that allows us to grab references to the parent containers, based on id
    var lookup = new Dictionary<int, List<Node>>();

    Queue<Node> nodeSet = new Queue<Node>();
    List<Node> children;

    foreach (Node item in list) {
        if (item.ParentId == 0) { // has no parent
            nodeSet.Enqueue(item); // This will add all root nodes in the forest
        } else {
            if (lookup.TryGetValue(item.ParentId, out children)) {
                // add to the parent's child list
                children.Add(item);
            } else {
                // no parent added yet
                lookup.Add(item.ParentId, new List<Node> { item });
            }
        }
    }

    while (nodeSet.Any()) {
        var node = nodeSet.Dequeue();
        if (lookup.TryGetValue(node.Id, out children)) {
            foreach (var child in children) {
                nodeSet.Enqueue(child);
            }
        }
        yield return node;
    }
}

private class Node {
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
}

Research

I did find this however it wasn't quite what I was after (also the code doesn't work)

Building hierarchy objects from flat list of parent/child

Can you _rely_ on `ParentId` being less than `Id`, or is that just coincidence here? — Rawling, Jan 30 '13 at 09:13

Carra · Answer 1 · 2013-01-30T09:16:18.833

-1

This code gives the same dump() result, order the list with parentid first:

IEnumerable<Node> SortHierarchy2(IEnumerable<Node> list)
{
    return list.OrderBy(l => l.ParentId);
}

This will work as long as your child ids are < their parents ids.

edited Jan 30 '13 at 09:16

answered Jan 30 '13 at 09:08

Carra

17,808
7
62
75

If child ids are always > parent ids, you can even order by `Id`. – Rawling Jan 30 '13 at 09:19
Just sorting by `ParentId` is way slower than the OP's method. That's why he asked for an algorithm suited for his special case. Sorting by `Id` is even slower. – sloth Jan 30 '13 at 15:40
How can sorting by Id be slower? It's O(n lg(n)). – Carra Jan 31 '13 at 09:38
After running it a few times, it's roughly as fast. Sometimes the sort is faster, sometimes the original method. – Carra Jan 31 '13 at 10:48

Efficient ordering of hierarchy data with only parentId

1 Answers1