How to efficiently build a tree from a flat structure?

Question

I have a bunch of objects in a flat structure. These objects have an ID and a ParentID property so they can be arranged in trees. They are in no particular order. Each ParentID property does not necessarily matches with an ID in the structure. Therefore their could be several trees emerging from these objects.

How would you process these objects to create the resulting trees ?

I'm not so far from a solution but I'm sure it is far from optimal...

I need to create these trees to then insert Data into a database, in proper order.

There are no circular references. A Node is a RootNode when ParentID == null or when ParentID can't be found in the other objects

Answer 1

Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly.

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}