Mapping a flat list to a hierarchical list with parent IDs C#

Question

I have a flat list of categories as shown in the following classes

public class FlatCategoryList
{
    public List<FlatCategory> Categories { get; set; }
}
public class FlatCategory
{
    public string ID { get; set; }
    public string Name { get; set; }
    public string ParentID { get; set; }
}

I'm trying to map my flat list of categories to a heirarical structure such as shown below:

public class HieraricalCategoryList
{
    public List<Category> Categories { get; set; }
}
public class Category
{
    public string ID { get; set; }
    public string Name { get; set; }
    public string ParentID { get; set; }

    public List<Category> ChildCategories { get; set; }
}

My question is, what is the best way to achieve this, given the fact that there could be an infinite number child tiers?

public HieraricalCategoryList MapCategories(FlatCategoryList flatCategoryList)
{
    var hieraricalCategoryList = new HieraricalCategoryList();

    //Do something here to map the flat category list to the hierarichal one...

    return hieraricalCategoryList;
}

Answer 1

public HieraricalCategoryList MapCategories(FlatCategoryList flatCategoryList)
{
    var categories = (from fc in flatCategoryList.Categories
                      select new Category() {
                          ID = fc.ID,
                          Name = fc.Name,
                          ParentID = fc.ParentID
                      }).ToList();

    var lookup = categories.ToLookup(c => c.ParentID);

    foreach(var c in categories)
    {
        // you can skip the check if you want an empty list instead of null
        // when there is no children
        if(lookup.Contains(c.ID))
            c.ChildCategories = lookup[c.ID].ToList();
    }

    return new HieraricalCategoryList() { Categories = categories };
}

Answer 2

A very easy and highly performant way to make this transformation is to create a lookup in which you map ID values to the nodes that should be the children of that ID value. This lookup can be created in a single pass of the nodes. After that you can iterate through all of the nodes again assigning their child collection to be the value of their ID value in the lookup.

Note that this is simpler if the lookup maps to objects of the type you are converting to, not converting from.

var lookup = list.Categories
    .Select(category => new Category()
    {
        ID = category.ID,
        Name = category.Name,
        ParentID = category.ParentID,
    })
    .ToLookup(category => category.ParentID);

foreach (var category in lookup.SelectMany(x => x))
    category.ChildCategories = lookup[category.ID].ToList();

var newList = new HieraricalCategoryList()
{
    Categories = lookup[null].ToList(),
};

Answer 3

Improved the suggested answer

public HieraricalCategoryList MapCategories(FlatCategoryList flatCategoryList)
{
    var categories = (from fc in flatCategoryList.Categories
                      select new Category() {
                          ID = fc.ID,
                          Name = fc.Name,
                          ParentID = fc.ParentID
                      }).ToList();

    var lookup = categories.ToLookup(c => c.ParentID);

    foreach(var c in rootCategories)//only loop through root categories
    {
        // you can skip the check if you want an empty list instead of null
        // when there is no children
        if(lookup.Contains(c.ID))
            c.ChildCategories = lookup[c.ID].ToList();
    }

    //if you want to return only root categories not all the flat list
    //with mapped child 

    categories.RemoveAll(c => c.ParentId != 0);//put what ever your parent id is

    return new HieraricalCategoryList() { Categories = categories };
}

Answer 4

Use a two-pass solution. This assumes the full collection can fit in memory. The first pass scans the list of flat categories, and builds a dictionary of Category, indexed by the ID. The child collections are all empty at this point, and the parent property is null. Then the second pass scans them again, and builds up the child collections and sets the parent property.

Untested code:

var final = new Dictionary<string, Category>();
var rootCategories = new List<Category>();

// Pass 1
foreach (var flat in flatList)
{
  Category cat = new Category() { ID = flat.ID, Name = flat.Name, parent = null }
  cat.Children = new List<Category>();
  final[flat.ID] = cat;
}

// Pass 2
foreach (var flat in flatList)
{
  // find myself -- must exist
  var self = final[flat.ID];

  // find parent -- may not exist
  if (final.ContainsKey(flat.ParentID)
  {
    var parent = final[flat.ParentID];
    parent.Children.Add(self);
    self.Parent = parent;     
  }
  else
  {
    rootCategories.Add(self);
  }

}

This will have O(n) running time, since it's two linear scans, with some dictionary lookups, which are O(1).