A recursive method for converting a flat collection to a hierarchical collection?

Question

I have been stuck in this problem for several days and would appreciate some ideas or help in solving it. I have a set of objects

public class Hierarchy { public Hierarchy(string iD, string name, int level, string parentID, string topParent) { ID = iD; Name = name; Level = level; ParentID = parentID; Children = new HashSet<Hierarchy>(); } public string ID { get; set; } public string Name{ get; set; } public int Level { get; set; } public string ParentID { get; set; } public ICollection<Hierarchy> Children { get; set; } } 

Linq query data for my object:

 ID Name Level ParentID 295152 name1 1 null 12345 child1 2 295152 54321 child2 2 295152 44444 child1a 3 12345 33333 child1b 3 12345 22222 child2a 3 54321 22221 child2b 3 54321 22002 child2c 3 54321 20001 child2a2 4 22222 20101 child2b2 4 22222 

This data may extend to unknown level depths (I show only 4). Ultimately, I would have one Hierarchy with a collection of several children, which, in turn, can have a collection of several children ... etc ... There will always be only one top-level object.

I am trying to use Linq as much as possible in this project.

This obviously needs some sort of recursive method, but I'm stuck. Any ideas or help would be appreciated.

TIA

Answer 1

You can try this recursive function:

 void PopulateChildren(Hierarchy root, ICollection<Hierarchy> source) { foreach (var hierarchy in source.Where(h => h.ParentID == root.ParentID)) { root.Children.Add(hierarchy); PopulateChildren(root, source); } } 

What you can use as follows:

 ICollection<Hierarchy> hierarchies = new List<Hierarchy>(); // source // Get root var root = hierarchies.Single(h => h.Level == 1); // Populate children recursively PopulateChildren(root, hierarchies); 

Answer 2

In fact, the iterative solution is probably much simpler. Here are the steps:

• Hash of all nodes in the dictionary based on their id
• Scroll a second time and add each node to its parent child list

Which looks like this:

 Hierarchy CreateTree(IEnumerable<Hierarchy> Nodes) { var idToNode = Nodes.ToDictionary(n => n.ID, n => n); Hierarchy root; foreach (var n in Nodes) { if (n.ID == null) { if (root != null) { //there are multiple roots in the data } root = n; continue; } Hierarchy parent; if (!idToNode.TryGetValue(n.ID, parent)) { //Parent doesn't exist, orphaned entry } parent.Children.Add(n); } if (root == null) { //There was no root element } return root; } 

There are some obvious possible errors in your data format. It is up to you what to do with them.

In general, there is always an iterative solution and a recursive solution. A private problem is changing, which is easier.