Creating a TreeNode hierarchy in C#

Question

The following function accepts a list of Topic entities, retrieved from a database using LINQ-to-Entities. Each Topic has an Id, Title and ParentId.

I want to populate an ASP.NET TreeView control, and so the function is creating a hierarchy of the Topics based on their ParentId. If a Topic has no parent, its ParentId is null and I put it under the 'root'.

public TreeNode GenerateTopicsTree(List<Topic> topics) {
  var s = new Stack<TreeNodeAndId>();
  var root = new TreeNode("Topics", "0");
  s.Push(new TreeNodeAndId { Id = null, TreeNode = root });
  while (s.Count > 0) {
    var node = s.Peek();
    var current = topics.FirstOrDefault(o => o.ParentId == node.Id);
    if (current == null) {
      s.Pop();
      continue;
    }
    var child = new TreeNode(current.Title, current.Id.ToString());
    node.TreeNode.ChildNodes.Add(child);
    s.Push(new TreeNodeAndId { Id = current.Id, TreeNode = child });
    topics.Remove(current);
  }
  return root;
}

struct TreeNodeAndId
{
  public TreeNode TreeNode;
  public int? Id;
}

Any improvements?

Answer 1

Just a word of advice, creating a mutable struct which is always a bad idea. It must be a class otherwise you're just leaving yourself open to problems and confusion.

You could improve it much more if you don't restrict your methods to use lists of topics. You could then easily apply recursion here and write it in a more functional style with simpler logic.

static TreeNode GenerateTopicsTree(IEnumerable<Topic> topics)
{
    // shouldn't the root value be null?
    var root = new TreeNode("Topics", null);
    return GenerateTopicSubTree(root, topics);
}

static TreeNode GenerateTopicSubTree(TreeNode root, IEnumerable<Topic> topics)
{
    // partition the topics to child and non-child topics
    var rootId = GetId(root);
    var childTopics = topics.ToLookup(topic => topic.ParentId == rootId);

    // create and add subtrees to the current node
    var childNodes = childTopics[true].Select(GenerateNode);
    foreach (var childNode in childNodes)
    {
        root.ChildNodes.Add(GenerateTopicSubTree(childNode, childTopics[false]));
    }
    return root;
}

static int? GetId(TreeNode node)
{
    int id;
    if (Int32.TryParse(node.Value, out id))
        return id;
    return null;
}

static TreeNode GenerateNode(Topic topic)
{
    return new TreeNode(topic.Title, Convert.ToString(topic.Id));
}

Consider using data binding to create your tree instead. I don't know how it works with ASP.NET so I can't really give you tips on how to do it. But doing so should make this step unnecessary as the framework will generate the tree for you. You'll probably have to create a class to represent the topics organized in a hierarchy but you could use the above code to create that hierarchy.

---

After thinking about this again, I think it would be better to just group them all at once in the beginning instead of partitioning at every step. Here's an alternate implementation:

static TreeNode GenerateTopicsTreeAlt(IEnumerable<Topic> topics)
{
    var root = new TreeNode("Topics", null);

    // group all children together now so we don't need to regroup them again later
    var childTopics = topics.ToLookup(topic => topic.ParentId);
    return GenerateTopicSubTreeAlt(root, childTopics);
}

static TreeNode GenerateTopicSubTreeAlt(TreeNode root, ILookup<int?, Topic> childTopics)
{
    // create and add subtrees to the current node
    var rootId = GetId(root);
    var childNodes = childTopics[rootId].Select(GenerateNode);
    foreach (var childNode in childNodes)
    {
        root.ChildNodes.Add(GenerateTopicSubTreeAlt(childNode, childTopics));
    }
    return root;
}