C# Recursively loop over object and return all children

Question

I've the following class, which contains some info about the object it also has a list of same object and hierarchy goes on. This is my class:

public class Category
{
    public List<Category>? children { get; set; }
    public bool var { get; set; }
    public string? name { get; set; }
    public bool leaf { get; set; }
    public int category_id { get; set; }
}

I have a list List<Category> categories; I want to loop over the list and go deep down in every children and create this new object:

public class DBCategory
{
    public string? CategoryId { get; set; }
    public string? CategoryName { get; set; }
    public string? CategoryParentId { get; set; }
}

I have tried to loop over my list and then call function recursively but I'm also stuck there because children isn't a category class but a list of categories so the function fails to accept parameter in if clause:

foreach (var category in categories)
{
    CreateDBCategory(category);
}

DBCategory CreateDBCategory(Category category)
{
    DBCategory dBCategory = new DBCategory();

    if (category.children.Count > 0)
    {
        return CreateDBCategory(category.children);
    }
    return dBCategory;
}

I have also tried to reach most bottom child by this, but this code says not all paths return a value.

DBCategory testFunction(List<Category> categories)
{
    foreach (var category in categories)
    {
        if (category.children.Count > 0)
        {
            return testFunction(category.children);
        }
        else
        {
            return category;
        }
    }

}

I have a problem, that I'm unable to understand how can I recursively reach to bottom child. — Muhammad Hassan Javed, Aug 25 '22 at 09:55
1) If I understand correctly, your CreateDBCategory should return a List, not a single object; 2) category.children may be null so check for that — Hans Keﬆing, Aug 25 '22 at 09:55
be careful with the performance, it is a recursive with Exponential order. — jmvcollaborator, Aug 25 '22 at 09:57
Since `category.children` is a `List` you'd obviously also need to loop over that (in the case it is not `null`) - and also your recursive method needs to add the elements to a list — UnholySheep, Aug 25 '22 at 09:57
Okay, so should my recursive method create a list on top, loop over my parameter, if children is not null, call the function again and pass the list otherwise add element to my created list in function and return that list at the end? @UnholySheep — Muhammad Hassan Javed, Aug 25 '22 at 10:03
you have a Tree structure what is the deal to traverse a tree ? — jmvcollaborator, Aug 25 '22 at 10:50

UnholySheep · Accepted Answer · 2022-08-25T10:22:09.750

One of the common ways to handle such cases is to have the List to be filled passed as an argument to the method. E.g.:

List<DBCategory> dbCategories = new();
foreach (var category in categories)
{
    CreateDBCategory(category, dbCategories);
}

void CreateDBCategory(Category category, List<DBCategory> dbCategories)
{
    DBCategory dbCategory = new DBCategory();
    // Fill dbCategory
    dBCategories.Add(dbCategory);

    if (category.children != null)
    {
        // recurse over all children categories and add them to the list
        foreach (var child in category.children)
        {
            CreateDBCategory(child, dbCategories);
        }
    }
}

It could be argued that this solution does not fit the functional paradigm as it has side effects (modifying the passed in List), so an alternative, more functional approach would be to return a list from the recursive method, e.g.:

List<DBCategory> dbCategories = new();
foreach (var category in categories)
{
    dbCategories.AddRange(CreateDBCategory(category));
}

IEnumerable<DBCategory> CreateDBCategory(Category category)
{
    List<DBCategory> dbCategories = new();
    DBCategory dbCategory = new DBCategory();
    // Fill dbCategory
    dbCategories.Add(dbCategory);

    if (category.children != null)
    {
        // recurse over all children categories and add them to the list
        foreach (var child in category.children)
        {
            dbCategories.AddRange(CreateDBCategory(child));
        }
    }

    return dbCategories;
}

This does however perform a lot more allocations, so in some cases it can perform slower than the first approach

score 1 · Answer 2 · answered Aug 25 '22 at 10:32

1

Noted that this is untested, but it should work.

IEnumerable<DBCategory> FlattenCategories(IEnumerable<Category> categories, int parentId) 
{
   DBCategory selector(Category cat, int pid) => 
   return categories
       .Select(c => new DBCategory {
            CategoryId = cat.category_id, 
            CategoryName = cat.name,
            CategoryParentId = pid,
       })
       .Concat(categories.SelectMany(
           c => FlattenCategories(c.children, c.category_id)
       );
}

Just call FlattenCategories(categories).ToList(); to get List<DBCategory>

answered Aug 25 '22 at 10:32

tia

9,518
1
30
44

good but, could have a stack overflow for a deep tree. – Jodrell Aug 25 '22 at 10:42
Yeah but it's categories so I assume shouldn't be that deep. 6 levels is quite deep already for categories. – tia Aug 25 '22 at 10:58

score 0 · Answer 3 · answered Aug 25 '22 at 10:36

From here, A generic solution.

public static IEnumerable<T> Traverse<T>(
    this T root,
    Func<T, IEnumerable<T>> childrenSelector)
{
    ArgumentNullException.ThrowIfNull(childrenSelector);
    
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in childrenSelector(current))
        {
            stack.Push(child);
        }
    }
}

So you can do this,

foreach(var category in root.Traverse(c => c.Children))
{
    ...
}

or some LINQ. The beauty is, it won't allocate more memory than your biggest leaf collection and won't have a stack overflow for deep trees.

If you're just copypasting from another answer, then shouldn't you be voting to close as a duplicate? — DavidG, Aug 25 '22 at 10:45

score -2 · Answer 4 · answered Aug 25 '22 at 10:21

Try following :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication40
{
    class Program
    {
 
        static void Main(string[] args)
        {
            Category root = new Category()
            {
                children = new List<Category>() {
                    new Category() {
                        children = new List<Category>() {
                            new Category() {
                                var = true,
                                name = "2A",
                                leaf = true,
                                category_id = 21
                            },
                            new Category() {
                                var = true,
                                name = "2B",
                                leaf = true,
                                category_id = 22
                            }
                        },
                        var = true,
                        name = "1A",
                        leaf = false,
                        category_id = 1
                    },   
                    new Category() {
                        children = new List<Category>() {
                            new Category() {
                                var = true,
                                name = "2C",
                                leaf = true,
                                category_id = 23
                            },
                            new Category() {
                                var = true,
                                name = "2D",
                                leaf = true,
                                category_id = 24
                            }
                        },
                        var = true,
                        name = "1B",
                        leaf = false,
                        category_id = 2
                    },
                },
                category_id = 0,
                name = "root",
                leaf = false,
                var = true
            };

            List<DBCategory> children = DBCategory.GetChildren(root,null);
 

 
        }
    }
    public class Category
    {
        public List<Category> children { get; set; }
        public bool var { get; set; }
        public string name { get; set; }
        public bool leaf { get; set; }
        public int category_id { get; set; }
    }
    public class DBCategory
    {
        public int? CategoryId { get; set; }
        public string CategoryName { get; set; }
        public int? CategoryParentId { get; set; }

        public static List<DBCategory> GetChildren(Category catgory, int? parentId)
        {
            List<DBCategory> results = new List<DBCategory>() { new DBCategory() { 
                CategoryId = catgory.category_id,
                CategoryName = catgory.name,
                CategoryParentId = parentId
            }};
            if (catgory.children != null)
            {
                foreach (Category child in catgory.children)
                {
                    results.AddRange(GetChildren(child, catgory.category_id));
                }
            }

            return results;
        }
    }
}

@Jodrell : The code is optimal and cannot be done any better. You comment doesn't make any sense. I added sample data to be able to test. — jdweng, Aug 25 '22 at 11:04
This is absolutely not optimal and can be done better - see other answers for example. Here you are creating a new list object at every level, and that is simply not necessary. — DavidG, Aug 25 '22 at 11:32
@DavidG : Were other answers tested? Using linq doesn't mean the list at every level isn't created. — jdweng, Aug 25 '22 at 12:04
It does mean that if the answer isn't recursive and doesn't even have a new `List` in it. Did you read the answer? Do you have any idea what is going on? — DavidG, Aug 25 '22 at 12:09

C# Recursively loop over object and return all children

4 Answers4