Building a tree out of items list

Question

I would like to get some suggestions on how I can build a tree out of items list in a efficient way

 public class Item
    {
        public Item(int id, int? parentId)
        {
            Id = id;
            ParentId = parentId;
        }

        public int Id { get; private set; }
        public int? ParentId { get; private set; }
        public List<Item> SubItems  { get; set; }
    }

    private Item BuildATree()
    {
        var items = new List<Item>()
                        {
                            new Item(1, null),
                            new Item(2, 1),
                            new Item(3, 1),
                            new Item(4, 1),
                            new Item(5, 2),
                            new Item(6, 2),
                            new Item(7, 4),
                            new Item(8, 7),
                            new Item(9, 1),
                        };

        //Build a tree out of list items
    }

The result I am expecting is each item being in its parent's SubItems list

Not necessarily using the same Item class, because Ids would be redundant then

Is this a homework since this structure has started to be a hot topic. http://stackoverflow.com/questions/10878268/recursive-reading-of-listobject , http://stackoverflow.com/questions/10827237/how-to-create-objects-with-retrieved-hierarchical-result-set — L.B, Jun 05 '12 at 12:08
This is not a homework, I am not asking for a solution, I am asking for some suggestions what would be most efficient way to solve it — Jeff, Jun 05 '12 at 12:23
What is your *inefficient* way that makes you seek for an efficient one ? — L.B, Jun 05 '12 at 12:27
Check out the update on post, well that is the solution which seems to be good enough for my case — Jeff, Jun 05 '12 at 12:45
@Jeff: If you have found/written the solution yourself then it would be nice if you add it as an answer to your own question and then accept it - just not to leave the open question hanging on SO. — Sergey Kudriavtsev, Jun 10 '12 at 21:47

Sergey Kudriavtsev · Answer 1 · 2012-06-05T12:40:15.027

I'd use LINQ:

//Build a tree out of list items
foreach (Item item in items)
{
    item.SubItems = items.Where(i => i.ParentId.Value == item.Id).ToList();
}

UPD:

To simplify moving items from one parent to another you'll need to store a reference to parent Item in every Item. Something like:

public class Item
{
    public Item(int id, int? parentId)
    {
        Id = id;
        ParentId = parentId;
    }

    public int Id { get; private set; }
    public int? ParentId { get; private set; }
    public List<Item> SubItems  { get; set; }

    private Item _parent;
    public Item Parent 
    {
        get { return _parent; }
        set
        {
            if (_parent != null)
                _parent.SubItems.Remove(this);
            _parent = value;
            if (_parent != null)
                _parent.SubItems.Add(this);
        }
    }
}

If you implement in that way then just setting new Parent item via this property will be enough to modify both old and new parent's SubItems collections - but beware that you'll also need a bit more complex list initialization mechanism.

Can it be recursive, also removing items from list if it was moved to Other item as a sub item — Jeff, Jun 05 '12 at 12:06
Item item in items...lol, thats got to be the most similar linq you can get without breaching on reserved keywords congratulations :P — RhysW, Jun 07 '12 at 12:54

score 2 · Accepted Answer · answered Jun 11 '12 at 11:46

Solution which is efficient enough

private void RecursiveBuilder(ref Item i, IEnumerable<Item> li)
{
    var item = i;
    i.SubItems = (from n in li where n.ParentId == item.Id select n).ToList();
    i.SubItems.ForEach(f => RecursiveBuilder(ref f, li));
}

wishper · Answer 3 · 2012-06-05T12:04:10.070

If you don't want/have Link :

Dictionary<int,Item> dic = new Dictionary<int,Item>();
foreach(Item item in items)
{
    Item parent;
    if(item.ParentId!=null && dic.TryGetValue(item.ParentId, out parent))
        parent.SubItems.Add(item);
    else
        dic.Add(item.Id, item);
}
Item root = dic[1];

I supposed that there will always be a Item with id = 1 and that's the root of the tree.

If you want to use new Class without the ids, create them instead of simply add them to their parents.

Building a tree out of items list

3 Answers3