How to flatten a tree into a list of objects in C#

Question

I have an app built on Blazor and .Net6. I have a hierarchy that I need to flatten into a list of objects that I can hook up to a Telerik grid.

A simplified version of my tree looks something like this. I can have N number "across" but limited to 5 "down".

Most of the articles I can find online are to flatten he tree into a linked list; that is not what I want. I want this. Each row in this grid is an object in a list.

The hierarchy comes from a self-joining table, which is each node in the hierarchy.

public class Taxonomy
{
    public int Id { get; set; }
    public string Name { get; set; }
    public int? ParentId { get; set; }
}

I need to get it into another object that represents each row in the grid. That object is

public class TaxonomyGrid
{
    public int? L1Id { get; set; }
    public string? L1 { get; set; }
    public int? L2Id { get; set; }
    public string? L2 { get; set; }
    public int? L3Id { get; set; }
    public string? L3 { get; set; }
    public int? L4Id { get; set; }
    public string? L4 { get; set; }
    public int? L5Id { get; set; }
    public string? L5 { get; set; }
}

Where am I right now? The code I wrote will walk down the first set of nodes. Take a look back at the tree diagram, the numbers in red are the order things are happening. This works fine and creates the first TaxonomyGrid object in the list. Then, it goes from H to G, which I expect but I'm not handling it correctly. The level counter resets to "1" and level 4 "G" is written to a TaxonomyGrid as level 1. Since it has no children, its the second object in the TaxonomyGrid list. Here's an example of what I'm getting out.

How do I track that's it's moving back up the hierarchy and build the objects appropriately? Once it hits Level 2, it will start working on "C" and the process starts over. Or, is there a better solution?

A quick overview of what the code is doing, I send in a root node Taxonomy and it recursively runs the function adding each level of the hierarchy to a workingTax object. Obviously the level is tracking the level on the hierarchy. Once there are no children its at the end of a node, it will add the workingTax to the TaxonomyGrid list.

public TaxonomyGridDTO GetAllChildren(List<TaxonomyDTO> Taxonomy, TaxonomyGridDTO workingTax = default, int level = 0)
{
    if (Taxonomy == null || !Taxonomy.Any())
        return new();

    level++;
    if(workingTax == null)
        workingTax = new();


    foreach (var item in Taxonomy) 
    { 
        switch (level)
        {
            case 1:
                workingTax.L1 = item.Name;
                workingTax.L1Id = item.TaxonomyId;
                break;

            case 2:
                workingTax.L2 = item.Name;
                workingTax.L2Id = item.TaxonomyId;

                item.ChildTaxonomy = TaxonomyList.Where(x => x.ParentId == item.TaxonomyId).ToList();
                break;

            case 3:
                workingTax.L3 = item.Name;
                workingTax.L3Id = item.TaxonomyId;

                item.ChildTaxonomy = TaxonomyList.Where(x => x.ParentId == item.TaxonomyId).ToList();
                break;

            case 4:
                workingTax.L4 = item.Name;
                workingTax.L4Id = item.TaxonomyId;

                item.ChildTaxonomy = TaxonomyList.Where(x => x.ParentId == item.TaxonomyId).ToList();
                break;

            case 5:
                workingTax.L5 = item.Name;
                workingTax.L5Id = item.TaxonomyId;
                break;
        }

        if (item.ChildTaxonomy != null && item.ChildTaxonomy.Any())
        {
            GetAllChildren(item.ChildTaxonomy, workingTax, level);
        }
        else
        {
            TaxonomyGrid.Add(workingTax);
            workingTax = new();
            level = 1;
        }
    }

    return workingTax;
}

Answer 1

Here's a methodology using recursion. I've made up some data. It needs a bit of tidying up and error trapping.

My data objects are record based value objects which simplify cloning.

public record Taxonomy(int Id, string Name, int? ParentId);

public record TaxonomyGrid
{
    public int? L1Id { get; init; }
    public string? L1 { get; init; }
    public int? L2Id { get; init; }
    public string? L2 { get; init; }
    public int? L3Id { get; init; }
    public string? L3 { get; init; }
    public int? L4Id { get; init; }
    public string? L4 { get; init; }
    public int? L5Id { get; init; }
    public string? L5 { get; init; }
}

public class TaxonomyProvider
{
    private List<Taxonomy> _taxonomies = new List<Taxonomy>();

    public TaxonomyProvider()
    {
        _taxonomies.Add(new(1, "World", 0));
        _taxonomies.Add(new(2, "Europe", 1));
        _taxonomies.Add(new(3, "Asia", 1));
        _taxonomies.Add(new(4, "Africa", 1));
        _taxonomies.Add(new(5, "France", 2));
        _taxonomies.Add(new(6, "Spain", 2));
        _taxonomies.Add(new(7, "Portugal", 2));
        _taxonomies.Add(new(8, "Cordoba", 6));
        _taxonomies.Add(new(9, "Algeciras", 6));
    }

    private List<TaxonomyGrid> _grid = new List<TaxonomyGrid>();

    public List<TaxonomyGrid> GetGrid()
    {
        _grid = new List<TaxonomyGrid>();

        GetLevel(0, 1, new());

        return _grid;
    }

    private void GetLevel(int id, int level, TaxonomyGrid gridItem)
    {
        var items = _taxonomies.Where(item => item.ParentId == id);

        foreach (var item in items)
        {
            var nextLevel = level + 1;
            var newGridItem = GetGridItem(item, level, gridItem);
            if (newGridItem is not null)
                GetLevel(item.Id, nextLevel, newGridItem);
        }


        if (gridItem != new TaxonomyGrid())
            _grid.Add(gridItem with { });
    }

    private TaxonomyGrid? GetGridItem(Taxonomy tax, int level, TaxonomyGrid gridItem)
    {
        var grid = level switch
        {
            1 => gridItem with { L1 = tax.Name, L1Id = tax.Id },
            2 => gridItem with { L2 = tax.Name, L2Id = tax.Id },
            3 => gridItem with { L3 = tax.Name, L3Id = tax.Id },
            4 => gridItem with { L4 = tax.Name, L4Id = tax.Id },
            5 => gridItem with { L5 = tax.Name, L5Id = tax.Id },
            _ => null
        };
        return grid;
    }
}