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:

Resistencia

@Nick - Can a top level category's (CD-DVD-Video) subcategory (CD audio) also have another sub category? In other words, could you have - CD-DVD-Video/CD audio/Cases? – Lettie

@thedugas, yes, it could have an infinite amount of levels. – Resistencia

This seems to be exactly the sort of situation for which tree controls were designed. Why use a list control? – Stortz

@Jerry Coffin, I need to assign products to categories, I believe a list control would be better considering the user can pick multiple categories. – Resistencia

you need to convert all results into the category list - you are only populating the ones with a parentid of 0 – Lettie

@thedugas, I modified the code above so that it initially stores List<Category> categories with the entire table, but I'm still getting the same results. When the code goes to evaulate var children = categories.Where(cats => cats.parentID == cats.categoryID); it finds none, which is strange because there is rows that have a parentID which matches parent rows ID. – Resistencia

@Nick - in my example, I used the subset of parents only in main before looping, you are calling on all in your page load (which explains the difference in results (the need for the prefix check). You can reduce the computations by only looping in your page load through Categories that have a ParentId of 0, not all of them after you contruct your categories list. – Lettie

I would note that you do not have an infinite number of subcategory levels. That is, you have no category which is actually 0/1/2/3/4/5/6/7/8/9/10/... on into infinity. What you actually have is a finite but unbounded number of category levels, right? Every category has a finite number of levels, but there is no bound on how high that finite number can be. – Ingaingaberg

@Eric Lippert, You are correct. I can't think of any reason why the client would need to go down more than 4 or 5 levels, but if they do it is possible to go as deep as needed. In this particular situation the user can click on the parent category and see items right away and have the ability to drill down deeper if they want to filter the results.(Newegg is set up like this). – Resistencia

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.

Ingaingaberg

This is very helpful. Thank you for taking the time to answer. – Resistencia

Why is string.Join inefficient here? Only reason I can think of is the Reverse... – Unjaundiced

@configurator: The naive string version is O(n^2) in time in the number of subcategories. The Join version is O(n) in extra memory due to the Reverse. Since the number of subcategories is likely to be small, it's probably a wash. – Ingaingaberg

Oh, I misread your text - I read it as "Or, if you prefer the potentially inefficient naive string concatenation" which didn't make much sense... – Unjaundiced

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

}

Lettie

thanks for writing that code, it's very helpful, can you take a look at my edit above? – Resistencia

I finally got it working, I had to make some changes to work with my solution, and fix two errors, but if you would like to update your answer I will accept it, as you laid out the groundwork for me. Thank you. – Resistencia

it looks like you fixed the children query already, but in the children foreach loop you should have if(prefix.Any()) to prevent the name of the sub category being listed by itself with no parent cat prefixing it. Regardless, thank you for your help, I couldn't of done it without your answer. – Resistencia

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

Manhandle