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.

• Alternatex: I'm accepting this because of the sheer simplicity.

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)
 };
 }
}