Turning a flat nested set into a hierarchy

Question

So I have categories in my database and I've implemented the Nested set model. I'm reading the categories as a flat structure and then I'm turning it into a hierarchy in memory, mapping each entity to a DTO.

Here's my code:

public async Task<IActionResult> GetCategories()
{
    var categories = (List<Category>)await _categoryService.GetAllAsync();

    var categoryDtos = GetCategoryDtosHierarchy(categories, null);

    categoryDtos.RemoveAll(x => x.Depth > 0); // Terrible

    return Ok(categoryDtos);
}

private List<CategoryDto> GetCategoryDtosHierarchy(List<Category> categories, Category parent)
{
    var categoryDtos = new List<CategoryDto>();
    var filteredCategories = categories;

    if (parent != null)
    {
        filteredCategories = categories.Where(x => x.Depth == (parent.Depth + 1) &&
                                                   x.Left > parent.Left &&
                                                   x.Right < parent.Right).ToList();
    }

    foreach (Category filteredCategory in filteredCategories)
    {
        var categoryDto = new CategoryDto
        {
            Id = filteredCategory.Id,
            Name = filteredCategory.Name,
            Depth = filteredCategory.Depth,
            SubCategories = GetCategoryDtosHierarchy(categories, filteredCategory)
        };

        categoryDtos.Add(categoryDto);
    }

    return categoryDtos;
}

So everything works but it feels like somewhat an awkward solution. When the GetCategoryDtosHierarchy(categories, null); line returns it not only returns the categories with their subcategories but every level below like so:

[
  {
    "name": "Clothing",
    "depth": 0,
    "subcategories": [
      {
        "name": "Men's",
        "depth": 1,
        "subcategories": [
          {
            "name": "Suits",
            "depth": 2,
            "subcategories": []
          }
        ]
      },
      {
        "name": "Women's",
        "depth": 1,
        "subcategories": []
      }
    ]
  },
  {
    "name": "Men's", // Not supposed to be here
    "depth": 1,
    "subcategories": [
      {
        "name": "Suits",
        "depth": 2,
        "subcategories": []
      }
    ]
  },
  {
    "name": "Women's", // Not supposed to be here
    "depth": 1,
    "subcategories": []
  },
  {
    "name": "Suits", // Not supposed to be here
    "depth": 2,
    "subcategories": []
  }
]

And it has forced me to run the categoryDtos.RemoveAll(x => x.Depth > 0); in order to get rid of the excess. I've thought about putting both calls in a new method but I feel like there might be a better solution than this hack.

Answer 1

What about idea (and removing categoryDtos.RemoveAll(x => x.Depth > 0); // Terrible):

if (parent != null)
{
    filteredCategories = categories.Where(x => x.Depth == (parent.Depth + 1) &&
                                               x.Left > parent.Left &&
                                               x.Right < parent.Right).ToList();
}
else
{
    filteredCategories = categories.Where(x => x.Depth == 0).ToList();
}

Or, if the function is used somwhere else as well, maybe additional parameter to function like bool onlyTopLevel.

Answer 2

As smartobelix mentioned, it makes sense to distinguish between loading root elements and loading non-root elements. I would prefer to use separate methods instead of using a flag and add a "if branch" in one method.

Another simplification is the usage of IEnumerable<T> and yield instead of creating temporary lists. That makes the code slim and readable.

A refactored version could look like:

public async Task<IActionResult> GetCategories()
{
    var categories = (List<Category>)await _categoryService.GetAllAsync();

    var categoryDtos = GetCategoryDtosRoot(categories).ToList();

    return Ok(categoryDtos);
}

private IEnumerable<CategoryDto> GetCategoryDtosRoot(List<Category> allCategories)
{
    var query = allCategories.Where(c => c.Depth == 0);
    return RunQueryRecursive(query, allCategories);
}

private IEnumerable<CategoryDto> GetCategoryDtosChildren(List<Category> allCategories, Category parent)
{
    var query = allCategories.Where(x => x.Depth == (parent.Depth + 1) 
                                        && x.Left > parent.Left 
                                        && x.Right < parent.Right).ToList();

    return RunQueryRecursive(query, allCategories);
}

private IEnumerable<CategoryDto> RunQueryRecursive(IEnumerable<Category> query, List<Category> allCategories)
{
    foreach (var category in query)
    {
        yield return new CategoryDto
        {
            Id = category.Id,
            Name = category.Name,
            Depth = category.Depth,
            SubCategories = GetCategoryDtosChildren(allCategories, category)
        };
    }
}