Build tree type list by recursively checking parent-child relationship C#

Question

I have One class that has a list of itself so it can be represented in a tree structure.

I am pulling a flat list of these classes and want to unflatten it.

public class Group {      public int ID {get;set;}       public int? ParentID {get;set;}       public List<Group> Children {get;set;}  } 

I want to be able to do the following

List<Group> flatList = GetFlatList() //I CAN ALREADY DO THIS List<Group> tree = BuildTree(flatList); 

The ParentID related to the ID property on its parent group if that wasnt obvious.

EDIT

There is some confusion as to why I am returning a list and not a single object.

I am building a UI element that has a list of items, each of why has a child. So the initial list DOES NOT have a root node. It seems all of the solutions so far do not work.

What this means is I essentially need a list of tree type structures using Group class.

Answer 1

I have no idea why you want your BuildTree method return List<Group> - tree needs to have root node, so you should expect it to return single Group element, not a list.

I would create an extension method on IEnumerable<Group>:

public static class GroupEnumerable {     public static IList<Group> BuildTree(this IEnumerable<Group> source)     {         var groups = source.GroupBy(i => i.ParentID);          var roots = groups.FirstOrDefault(g => g.Key.HasValue == false).ToList();          if (roots.Count > 0)         {             var dict = groups.Where(g => g.Key.HasValue).ToDictionary(g => g.Key.Value, g => g.ToList());             for (int i = 0; i < roots.Count; i++)                 AddChildren(roots[i], dict);         }          return roots;     }      private static void AddChildren(Group node, IDictionary<int, List<Group>> source)     {         if (source.ContainsKey(node.ID))         {             node.Children = source[node.ID];             for (int i = 0; i < node.Children.Count; i++)                 AddChildren(node.Children[i], source);         }         else         {             node.Children = new List<Group>();         }     } } 

Usage

var flatList = new List<Group>() {     new Group() { ID = 1, ParentID = null },    // root node     new Group() { ID = 2, ParentID = 1 },     new Group() { ID = 3, ParentID = 1 },     new Group() { ID = 4, ParentID = 3 },     new Group() { ID = 5, ParentID = 4 },     new Group() { ID = 6, ParentID = 4 } };   var tree = flatList.BuildTree();