Matching a flat list to a hierarchical list with C # parent identifiers

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 am trying to match my flat list of categories with a hierarchical 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 can be an infinite number of child levels?

 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 simple and highly efficient way to do this conversion is to create a search in which you map the identifier values ​​to the nodes, which should be children of this identifier value. This search can be created in a single pass through the nodes. After that, you can iterate over all the nodes, again assigning their child collection the value of their identifier in the search.

Note that this is easier if the search is mapped to objects of the type you are converting to, and not to conversion.

 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

Use a two-pass solution. This suggests that a complete collection can fit in memory. The first pass looks through a list of flat categories and builds a category dictionary indexed by identifier. At this point, the child collections are empty, and the parent property is null. Then the second pass scans them again and creates child collections and sets the parent property.

Unverified 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 be the O (n) runtime, as these are two linear scans with some dictionary searches that are O (1).