Building Trees from Lists in .NET

• Download source code for .NET 2.0 projects - 3.29 KB
  (A single CS file to be included in your .NET 2.0 project)
• Download source code for .NET 3.5 projects - 3.29 KB
  (A single CS file to be included in your .NET 3.5+ project)

Who Is This Article For?

This article is aimed at .NET developers who need to build a tree (or forest) of objects by loading an array or list of rows from a database, and converting them to a tree structure in memory to use or display.

Introduction

Storing hierarchical data in a database is a very common requirement, whether it be product categories, sports tournaments, or staff hierarchies. Over the years, I have had to create, store in a database and display trees many times, and my method has evolved from having fixed-size hierarchies, to abstract classes providing tree functionality, and finally to the method described in this article. This article describes a very simple way to load data from a table, and convert it into a tree in C# code for .NET 2.0+.

While other articles have been written on the subject, the following goals are not always met:

• You should not need to extend an abstract class, because your data class may already extend another class
• You shouldn't need to convert your class to be a partial class
• You shouldn't need to change your database table: as long as it uses the standard parent ID column referring to its own primary key, it should work
• There shouldn't need to be any type-casting of parent or child objects
• It should be easy to use

The answer is to define an interface - in this case called ITreeNode<t /> - and then have a utility method to build a tree from that. This article assumes that you have a class defined to hold a single node (e.g. a Category object), and that when you get a list of nodes from the database each reference to a parent has been instantiated as an object with its ID set, but without a reference to the fully populated parent object, nor its children.

An Example

Let's look at the very common "Category" entity, used to categorise products. The database table looks like the following:

Let's assume that there are just 8 rows in the database, which break the products into two main categories - "Hardware" and "Software" - and then further sub-categories. In this case "Operating Systems" and "Developer Tools" come under "Software"; "Monitors" and "Peripherals" under "Hardware", and finally "Keyboards" and "Mice" under "Peripherals", giving the following category hierarchy:

In the database, the rows are as follows:

In order to display this information on a website, you create a "Category" class:

public class Category
{
    private int _id;
    private string _name;
    private Category _parent;
    private List<Category> _children;
    
    public int Id
    {
        get { return _id; }
        set { _id = value; }
    }

    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }

    public Category Parent
    {
        get { return _parent; }
        set { _parent = value; }
    }

    public List<Category> Children
    {
        get { return _children; }
        set { _children = value; }
    }
}

A method is also needed to retrieve all the categories from the database. This will be a "flat" list of each category, i.e. the _parent field will point to an object which only has its ID populated, and _children will be null. A possible example of this method is shown here:

static List<Category> GetListFromDatabase(DbConnection con) {
    DbCommand cmd = con.CreateCommand();
    cmd.CommandText = "SELECT Id, Name, ParentID FROM Category";
    cmd.CommandType = CommandType.Text;
    DbDataReader reader = cmd.ExecuteReader();
    List<Category> categories = new List<Category>(); 
    foreach (DbDataRecord row in reader) {
        Category c = new Category();
        c.Id = (int)row["Id"];
        c.Name = (string)row["Name"];
        if (row["ParentID"] != DBNull.Value)
        {
            c.Parent = new Category();
            c.Parent.Id = (int)row["ParentID"];
        }
        categories.Add(c);
    }
    reader.Close();
    return categories;
}

Once having a list of objects in memory, the ITreeNode interface comes in handy. The first step is to implement this interface:

public class Category : ITreeNode<Category> {
// contents of class remain as above, because the 
// interface is implemented by the Id, Parent, and 
// Children properties
}

The interface requires that we have one property referring to the parent of the category (where null represents a root-level node), and an IList pointing to the children.

Now we can call the TreeHelper utility methods to convert the flat array returned from GetListFromDatabase into a fully populated hierarchy:

IList<Category> topLevelCategories = 
    TreeHelper.ConvertToForest(GetListFromDatabase());

The variable topLevelCategories contains two Categories: "Software" and "Hardware".

Printing Out All Nodes using Nested HTML <ul> and <li> Tags

Using a recursive method, you can easily print out, for example, the full category hierarchy in nested <ul> tags, as follows:

void Page_Load(object sender, EventArgs e) {
    IList<Category> topLevelCategories = 
        TreeHelper.ConvertToForest(Category.GetListFromDatabase());
    Response.Write("<ul>");
    foreach(Category topLevelCategory in topLevelCategories) {
        RenderCategory(topLevelCategory);
    }
    Response.Write("</ul>");
}

void RenderCategory(Category category) {
    Response.Write("<li>" + category.Name);
    if (category.Children.Count > 0) {
        Response.Write("<ul>");
        foreach(Category child in category.Children) {
            RenderCategory(child);
        }
        Response.Write("</ul>");
    }
    Response.Write("</li>");
}

This will render the following output:

• Software
  • Operating Systems
  • Developer Tools
• Hardware
  • Monitors
  • Peripherals
    • Keyboards
    • Mice

Searching For a Single Category in the Tree

// in a website, this may use the ASP.NET Cache object.
List<Category> categories = GetCategories();
int categoryId = int.Parse(Request.Params["categoryId"]); 
Category currentCategory = 
    TreeHelper.FindTreeNode(categories, categoryId);

Printing Breadcrumbs

Continuing the example above, this is how the bread crumbs for the current category could be printed:

Category currentCategory = GetCategory();
foreach(Category category in 
    TreeHelper.Iterators.FromRootToNode(currentCategory))
{
    Response.Write(" / " + category.Name);
}

If the current category was "Keyboards", this would render the following HTML:

/ Hardware / Peripherals / Keyboards

Tree Helper

The TreeHelper utility class contains numerous other useful methods - such as GetDepth and HasHierarchyLoop - and iterators - such as DepthFirstTraversal, BreadthFirstTraversal, ClimbToRoot, FromRootToNode, and Siblings.

Check out the fully-documented source code for the full details.

Using Extension Methods and "LINQ to Trees"

If you are using a .NET 3.5 solution, you are able to take advantage of extension methods. This has the effect of implementing methods in interface declarations (which is not possible in older versions of C#), which is probably the most useful aspect of extension methods, and indeed was the reason they were invented.

An example using extension methods:

List<Category> categories = GetCategories().ConvertToForest();
Category current = categories.FindCategory(3);
foreach(Category descendent in current.DepthFirstTraversal()) {
    Response.Write("Depth of " + descendent.Name + ": " + descendent.GetDepth();
}

Remember, ConvertToForest, FindCategory, DepthFirstTraversal and GetDepth are not implemented by the Category class, it simply "inherits" these methods from the TreeHelper class, simply by implementing ITreeNode<T>.

Extension methods go hand-in-hand with LINQ. Yes, strictly speaking, this is simply "LINQ to Objects" rather than "LINQ to trees", but regardless, it is a new way to query your trees:

List<Category> categoryList = Category.GetCategories();

// Get all categories which are not top level categories, 
// and retrieve only the name.
var nonRootCategories = 
    from c in categoryList.DepthFirstTraversalOfList()
    where c.Parent != null
    select new { Name = c.Name };

// Get all categories at Depth 2, ordered by name, and
// get the whole category object.
var level2Categories = 
    from c in categoryList.DepthFirstTraversalOfList()
    where c.GetDepth() == 2
    orderby c.Name ascending
    select c;

Some Cool Stuff

The following .NET language features have made this class much more useful:

• Interfaces using Generic parameters. Note that the interface definition is ITreeNode<T>, and the reference to the parent, for example, is T Parent. This means you never need to cast from ITreeNode to your class.
• Creating iterators using the "yield" keyword. This is perhaps one of the more under-rated features introduced in .NET 2.0 which makes creating Iterators so easy. Check out the methods in the TreeHelper<T>.Iterators class.
• Extension methods and LINQ. Querying trees with LINQ can certainly make certain tasks much easier... and fun.

History

• 27^th February, 2008: Initial release
• 2^nd March 2008: Changed TreeHelper from a generic class to non-generic class with generic methods (to allow type method inference), and added the section on LINQ.