By Rami Shareef


2012-02-23 07:49:27 8 Comments

MyClass consists of ID ParentID and List<MyClass> as Children

I have list of MyClass like this

ID  ParentID
1   0
2   7
3   1
4   5
5   1
6   2
7   1
8   6
9   0
10  9

Output (Hierarchical list) as List<MyClass>

1 __ 3
 |__ 5__ 4
 |__ 7__ 2__ 6__ 8
     |__ 11

9 __10

What is the simplest way to achieve this in linq?
P.S.: ParentID not sorted

Edit:
My try:

class MyClass
{
    public int ID;
    public int ParentID;
    public List<MyClass> Children = new List<MyClass>();
    public MyClass(int id, int parent_id)
    {
        ID = id;
        ParentID = parent_id;
    }
}

initialize sample data and try to reach hierarchical data

 List<MyClass> items = new List<MyClass>()
{
    new MyClass(1, 0), 
    new MyClass(2, 7), 
    new MyClass(3, 1), 
    new MyClass(4, 5), 
    new MyClass(5, 1), 
    new MyClass(6, 2), 
    new MyClass(7,1), 
    new MyClass(8, 6), 
    new MyClass(9, 0), 
    new MyClass(10, 9), 
    new MyClass(11, 7), 
};

Dictionary<int, MyClass> dic = items.ToDictionary(ee => ee.ID);

foreach (var c in items)
    if (dic.ContainsKey(c.ParentID))
        dic[c.ParentID].Children.Add(c);

as you can see, lots of items I don't want still in the dictionary

3 comments

@JLRishe 2013-01-23 06:27:06

Recursion is not necessary here if you build the parent-child relationships before filtering. Since the members of the list remain the same objects, as long as you associate each member of the list with its immediate children, all of the necessary relationships will be built.

This can be done in two lines:

items.ForEach(item => item.Children = items.Where(child => child.ParentID == item.ID)
                                           .ToList());
List<MyClass> topItems = items.Where(item => item.ParentID == 0).ToList();

@Sarin 2013-04-04 22:05:07

I did not think of that. You're correct. Creating the hierarchy does not require recursion, only traversing does.

@DiVan 2013-06-04 05:48:33

Traversing does not too. :)

@Three Value Logic 2014-12-10 13:37:11

Just used this for a similar project. Beautiful solution and efficient too.

@arjthakur 2014-04-01 10:05:11

I have required such functionality and compare both methods and find method 2nd is faster than 1st :), right now in my database cards or records are limited but 1st method taking 4 times more time to complete.

may be this can help for those who are conscious about time.

1 method


    public JsonResult CardData()
    {
        var watch = System.Diagnostics.Stopwatch.StartNew();
        OrgChartWithApiContext db = new OrgChartWithApiContext();

        var items = db.Cards.ToList();
        Action<Card> SetChildren = null;
        SetChildren = parent => {
            parent.Children = items
                .Where(childItem => childItem.ParentId == parent.id)
                .ToList();

            //Recursively call the SetChildren method for each child.
            parent.Children
                .ForEach(SetChildren);
        };

        //Initialize the hierarchical list to root level items
        List<Card> hierarchicalItems = items
            .Where(rootItem => !rootItem.ParentId.HasValue)
            .ToList();

        //Call the SetChildren method to set the children on each root level item.
        hierarchicalItems.ForEach(SetChildren);
        watch.Stop();
        var timetaken = watch.ElapsedMilliseconds;

        return new JsonResult() { Data = hierarchicalItems, ContentType = "Json", JsonRequestBehavior = JsonRequestBehavior.AllowGet };
    }

method 2


    public JsonResult Card2Data()
    {
        var watch = System.Diagnostics.Stopwatch.StartNew();
        OrgChartWithApiContext db = new OrgChartWithApiContext();
        var items = db.Cards.ToList();
        List<Card> topItems = items.Where(item => !item.ParentId.HasValue).ToList();
        topItems.ForEach(item => item.Children = items.Where(child => child.ParentId == item.id).ToList());
        watch.Stop();
        var timetaken = watch.ElapsedMilliseconds;
        return new JsonResult() { Data = topItems, ContentType = "Json", JsonRequestBehavior = JsonRequestBehavior.AllowGet };
    }

@Sarin 2012-02-25 01:48:57

For hierarchical data, you need recursion - a foreach loop won't suffice.

Action<MyClass> SetChildren = null;
SetChildren = parent =>
    {
        parent.Children = items
            .Where(childItem => childItem.ParentID == parent.ID)
            .ToList();

        //Recursively call the SetChildren method for each child.
        parent.Children
            .ForEach(SetChildren);
    };

//Initialize the hierarchical list to root level items
List<MyClass> hierarchicalItems = items
    .Where(rootItem => rootItem.ParentID == 0)
    .ToList();

//Call the SetChildren method to set the children on each root level item.
hierarchicalItems.ForEach(SetChildren);

items is the same list you use. Notice how the SetChildren method is called within itself. This is what constructs the hierarchy.

@Andrew Hanlon 2014-09-28 13:27:49

This is less performant than the OPs original code. The dictionary method is far superior.

@Shailesh 2016-05-31 11:40:16

Nice user347805, Its working for me

@Kira Hao 2017-02-12 03:42:15

This is nice trick..!! it work for me too..!!

@Stfvns 2017-07-20 09:17:42

@user347805 @RamiShareef I want the output list add like print |__|__11 if that is a child. and if that is a parent just print 1. help please. thank

Related Questions

Sponsored Content

20 Answered Questions

11 Answered Questions

[SOLVED] Getting the last element of a list

  • 2009-05-30 19:28:53
  • Janusz
  • 1658558 View
  • 1711 Score
  • 11 Answer
  • Tags:   python list indexing

7 Answered Questions

[SOLVED] How do I get the number of elements in a list?

  • 2009-11-11 00:30:54
  • y2k
  • 3085237 View
  • 1783 Score
  • 7 Answer
  • Tags:   python list

39 Answered Questions

[SOLVED] How to make a flat list out of list of lists

25 Answered Questions

[SOLVED] How do I concatenate two lists in Python?

58 Answered Questions

[SOLVED] How do you split a list into evenly sized chunks?

30 Answered Questions

[SOLVED] How do I check if a list is empty?

  • 2008-09-10 06:20:11
  • Ray Vega
  • 2268190 View
  • 3236 Score
  • 30 Answer
  • Tags:   python list

15 Answered Questions

[SOLVED] How to clone or copy a list?

28 Answered Questions

[SOLVED] Finding the index of an item given a list containing it in Python

  • 2008-10-07 01:39:38
  • Eugene M
  • 3287076 View
  • 2704 Score
  • 28 Answer
  • Tags:   python list indexing

7 Answered Questions

Sponsored Content