Building a tree using a list of objects

Question

I have a list of objects with property id and parent_id.
I want to build a tree to link up those children and parents.
1 parent may have several children and there is an object which will be the ancestor of all objects.

What's the fastest algorithm to implement that?
I use C# as programming language, but other languages are also okay.

Answer 1

You could use a dictionary:

var dict = new Dictionary<Id, Node>();

foreach (var item in items)
{
    dict[item.Id] = new Node(item);
}

foreach (var item in items)
{
    dict[item.ParentId].AddChild(dict[item.Id]);
}

Answer 2

Something like that should do the trick :

public List<Node> MakeTreeFromFlatList(IEnumerable<Node> flatList)
{
    var dic = flatList.ToDictionary(n => n.Id, n => n);
    var rootNodes = new List<Node>();
    foreach(var node in flatList)
    {
        if (node.ParentId.HasValue)
        {
            Node parent = dic[node.ParentId.Value];
            node.Parent = parent;
            parent.Children.Add(node);
        }
        else
        {
            rootNodes.Add(node);
        }
    }
    return rootNodes;
}

(assuming that ParentId is a Nullable<int>, and is null for root nodes)