CODEWITHSUNDEEP
c#algorithmlanguage-agnostic
Billy
Billy

Reputation: 15706

Building a tree using a list of objects

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.

Upvotes: 5

Views: 7258

Answers (3)

Ewan
Ewan

Reputation: 1310

I much prefer this kind of structure. By maintaining a single list (you may want to use a dictionary or similar for speed) of items and passing it into the GetChildItems function you have greater flexibilty and ease of sorting, adding, removing, saving to a db etc.

You only really need the GetChildItem function when you are rendering the list to a view and you want the tree structure for easy editing as you say. In this case you can have a view model with the full list and the item which is passed into each item view

public class Item
{
    public string Id { get; set; }
    public string ParentId { get; set; }

    public IEnumerable<Item> GetChildItems(List<Item> allItems)
    {
        return allItems.Where(i => i.Id == this.ParentId);
    }
}

public class Tree
{
    public List<Item> Items { get; set; }

    public IEnumerable<Item> RootItems(List<Item> allItems)
    {
        return allItems.Where(i => i.ParentId == null);
    }
}

Note: the class structure above is designed to mimic the traditional complex object pattern. these days you would prob just have GetChildItems(List allItems, Item parentItem) in the view model

Upvotes: 1

Thomas Levesque
Thomas Levesque

Reputation: 292555

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)

Upvotes: 4

dtb
dtb

Reputation: 217351

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]);
}

Upvotes: 3

Related Questions