How can I populate a list box with many categories using recursive programming

Question

I have a categories table which is set up to allow an infinite number of sub category levels. I would like to mimic the following:

It should be clarified that sub categories can have sub categories. E.g. Parent cat -> level 1 -> level 2 -> level 3 etc.

My categories table has two columns, CategoryName and ParentID.

This list box will be used when assigning the correct category to a product.

How can I write this?

Edit

In response to thedugas I had to modify your answer to work with my situation. I found some errors that needed to be fixed, but below is a final, working solution.

protected void Page_Load(object sender, EventArgs e)
    {
        using (DataClasses1DataContext db = new DataClasses1DataContext())
        {

        var c = db.Categories.Select(x => x);

        List<Category> categories = new List<Category>();
        foreach (var n in c)
        {
            categories.Add(new Category()
            {
                categoryID = n.categoryID,
                title = n.title,
                parentID = n.parentID,
                isVisible = n.isVisible
            });
        }
        List<string> xx = new List<string>();

        foreach (Category cat in categories)
        {
            BuildCatString(string.Empty, cat, categories, xx);
        }

        ListBox1.DataSource = xx;
        ListBox1.DataBind();

    }
}

private void BuildCatString(string prefix, Category cat, IEnumerable<Category> categories, List<string> xx)
{
    if (cat.parentID == 0)
    {
        xx.Add(cat.title);
        prefix = cat.title;
    }

    var children = categories.Where(x => x.parentID == cat.categoryID);
    if (children.Count() == 0)
    {
        return;
    }

    foreach (Category child in children)
    {
        if(prefix.Any())
        {
        xx.Add(prefix + "/" + child.title);
        BuildCatString(prefix + "/" + child.title,
            child, categories, xx);
        }
    }

}

Here is the almost finished work:

Answer 1

Nick asked me in a comment to another question how this sort of problem might be solved using LINQ to Objects without using any recursion. Easily done.

Let's suppose that we have a Dictionary<Id, Category> that maps ids to categories. Each category has three fields: Id, ParentId and Name. Let's presume that ParentId can be null, to mark those categories that are "top level".

The desired output is a sequence of strings where each string is the "fully-qualified" name of the category.

The solution is straightforward. We begin by defining a helper method:

public static IEnumerable<Category> CategoryAndParents(this Dictionary<Id, Category> map, Id id)
{
    Id current = id;
    while(current != null)
    {
        Category category = map[current];
        yield return category;
        current = category.ParentId;
    }
}

And this helper method:

public static string FullName(this Dictionary<Id, Category> map, Id id)
{
    return map.CategoryAndParents(id)
              .Aggregate("", (string name, Category cat) =>
                cat.Name + (name == "" ? "" : @"/") + name);
}

Or, if you prefer avoiding the potentially inefficient naive string concatenation:

public static string FullName(this Dictionary<Id, Category> map, Id id)
{
    return string.Join(@"/", map.CategoryAndParents(id)
                                .Select(cat=>cat.Name)
                                .Reverse());
}

And now the query is straightforward:

fullNames = from id in map.Keys
            select map.FullName(id);
listBox.DataSource = fullNames.ToList();

No recursion necessary.

Answer 2

I would say to use a recursive CTE in SQL if you can. Edit: here is a recursive CTE for MS SQL >= 2005:

; WITH cte AS (
select CategoryId, CategoryName, ParentId,
cast(CategoryName as varchar(max)) as xpath
from 
categories
where ParentId = 0
UNION ALL
select c.CategoryId, c.CategoryName, c.ParentId, 
cast(p.xpath + '/' + c.CategoryName as varchar(max)) as xpath
from categories c inner join cte p on p.CategoryId = c.ParentId
)
select xpath from cte 
order by xpath

If you can't then here is one way:

class Category
{
        public int ParentId { get; set; }
        public int CategoryId { get; set; }
        public string CategoryName { get; set; }

        public static void BuildCatStringList(string prefix, Category c, 
                           IEnumerable<Category> categories, List<string> catStrings)
        {
            if (c.ParentId == 0)
            {
                catStrings.Add(c.CategoryName);
                prefix = c.CategoryName;
            }

            var children = categories.Where(cats => cats.ParentId == c.CategoryId);
            if (children.Count() == 0)
            {
                return;
            }

            foreach (Category child in children)
            {
                catStrings.Add(prefix + "/" + child.CategoryName);
                BuildCatStringList(prefix + "/" + child.CategoryName, 
                                   child, categories, catStrings);
            }
}


static void Main(string[] args)
{
        List<Category> categories = new List<Category>();
        categories.Add(new Category() { ParentId = 0, 
            CategoryName = "CD-DVD-Video", CategoryId=1 });
        categories.Add(new Category() { ParentId = 1, 
            CategoryName = "DVD", CategoryId = 10 });
        categories.Add(new Category() { ParentId = 1, 
            CategoryName = "Video cassettes", CategoryId= 11 });

        categories.Add(new Category() { ParentId = 0, 
            CategoryName = "Computer Hardware", CategoryId= 2 });
        categories.Add(new Category() { ParentId = 2, 
            CategoryName = "CD & DVD", CategoryId = 12 });
        categories.Add(new Category() { ParentId = 2, 
            CategoryName = "CPU Coolers", CategoryId = 13 });
        categories.Add(new Category() { ParentId = 2, 
            CategoryName = "Cases", CategoryId = 14 });
        categories.Add(new Category() { ParentId = 2, 
            CategoryName = "Keyboards", CategoryId = 15 });

        List<String> x = new List<string>();
        foreach (Category cat in categories.Where(c => c.ParentId == 0))
        {                
            Category.BuildCatStringList(String.Empty, cat, categories, x);
        }

}

Answer 3

Assuming the ParentID will be NULL for the Top Category. I would go for:

• Hold the data in a dataset Order By ParentID , CategoryName. lets say dataset1

string MainCategory as string="";

For(int i=0;i<=dataset1.CategoryTable.Rows-1;i++)
{
   if (dataset1.CategoryTable[i]["ParentID"] == DBNull.value) 
   {
       MainCategory= Convert.Tostring(dataset1.CategoryTable[i]["CategoryName"]);
   }
   else
   {
       // Add to the list
       List1.Add(MainCategory + Convert.Tostring(dataset1.CategoryTable[i]["CategoryName"]));
   }
}