Creating a Nested List from a Flat List in C#

Question

I currently have the following classes:

public class NavigationItem
{
    public int ID { get; set; }
    public string Title { get; set; }
    public int ParentID { get; set; }
    public List<NavigationItem> Children { get; set; }
}

public class FlatItem
{
    public int ID { get; set; }
    public string Title { get; set; }
    public int ParentID { get; set; }
}

I have a sample data as follows:

+====+============+==========+
| ID |   Title    | ParentID |
+====+============+==========+
|  1 | Google     |          |
+----+------------+----------+
|  2 | Microsoft  |          |
+----+------------+----------+
|  3 | Oracle     |          |
+----+------------+----------+
|  4 | Gmail      |        1 |
+----+------------+----------+
|  5 | Sheets     |        1 |
+----+------------+----------+
|  6 | Adsense    |        1 |
+----+------------+----------+
|  7 | Azure      |        2 |
+----+------------+----------+
|  8 | SharePoint |        2 |
+----+------------+----------+
|  9 | Office     |        2 |
+----+------------+----------+
| 10 | Java       |        3 |
+----+------------+----------+
| 11 | Word       |        9 |
+----+------------+----------+
| 12 | Excel      |        9 |
+----+------------+----------+
| 13 | PowerPoint |        9 |
+----+------------+----------+

I already have the code to pull all the information from the sample data above and turn it into a List<FlatItem> object.

What's the best approach so that I can have a List<NavigationItem> object which will look like something below:

• Google
  • Gmail
  • Sheets
  • AdSense
• Microsoft
  • Azure
  • SharePoint
  • Office
    • Word
    • Excel
    • PowerPoint
• Oracle
  • Java

I'm thinking of creating a recursive method to loop through my List<FlatItem> then structure it in a way to be a nested list of NavigationItem.

Answer 1

No need for recursion. You could use LINQ to build the structure easily:

List<FlatItem> flatItems = ...;

var navigationItems = flatItems.Select(
    i => new NavigationItem { ID = i.ID, Title = i.Title, ParentID = i.ParentID }
).ToList();

foreach (var i in navigationItems)
    i.Children = navigationItems.Where(n => n.ParentID == i.ID).ToList();

// get Google, Microsoft, Oracle items
var rootNavigationItems = navigationItems.Where(n => n.ParentID == 0);

Answer 2

Try this:

List<FlatItem> source = new List<UserQuery.FlatItem>()
{
    new FlatItem() { ID = 1, Title = "Google", ParentID = null },
    new FlatItem() { ID = 2, Title = "Microsoft", ParentID = null },
    new FlatItem() { ID = 3, Title = "Oracle", ParentID = null },
    new FlatItem() { ID = 4, Title = "Gmail", ParentID = 1 },
    new FlatItem() { ID = 5, Title = "Sheets", ParentID = 1 },
    new FlatItem() { ID = 6, Title = "Adsense", ParentID = 1 },
    new FlatItem() { ID = 7, Title = "Azure", ParentID = 2 },
    new FlatItem() { ID = 8, Title = "SharePoint", ParentID = 2 },
    new FlatItem() { ID = 9, Title = "Office", ParentID = 2 },
    new FlatItem() { ID = 10, Title = "Java", ParentID = 3 },
    new FlatItem() { ID = 11, Title = "Word", ParentID = 9 },
    new FlatItem() { ID = 12, Title = "Excel", ParentID = 9 },
    new FlatItem() { ID = 13, Title = "PowerPoint", ParentID = 9 },
};

var lookup = source.ToLookup(x => x.ParentID);

Func<int?, List<NavigationItem>> build = null;
build = pid =>
    lookup[pid]
        .Select(x => new NavigationItem()
        {
            ID = x.ID,
            Title = x.Title,
            ParentID = x.ParentID,
            Children = build(x.ID)
        })
        .ToList();

To start the process call build(null). That gives me this:

This does assume that the ParentId property is a int? - which your data table does suggest.