Populate a tree from Hierarchical data using 1 LINQ statement

Question

Hi. I have set up this programming exercise.

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

namespace ConsoleApplication2
{

    class DataObject {
       public int ID { get; set; }
       public int ParentID { get; set; }
       public string Data { get; set; }
       public  DataObject(int id, int pid, string data) { this.ID = id; this.ParentID = pid; this.Data = data; }
    }

    class TreeNode {
        public DataObject Data {get;set;}
        public List<DataObject> Children { get; set; }
    }


    class Program
    {

        static void Main(string[] args)
        {
            List<DataObject> data = new List<DataObject>();
            data.Add(new DataObject(1, 0, "Item 1"));
            data.Add(new DataObject(2, 0, "Item 2"));
            data.Add(new DataObject(21, 2, "Item 2.1"));
            data.Add(new DataObject(22, 2, "Item 2.2"));
            data.Add(new DataObject(221, 22, "Item 2.2.1"));
            data.Add(new DataObject(3, 0, "Item 3"));

        }
    }
}

The desired output is a List of 3 treenodes, having items 1, 2 and 3. Item 2 will have a list of 2 dataobjects as its children member and so on.

I have been trying to populate this tree (or rather a forest) using just 1 statement in LINQ. A simple group by gives me the desired data but the challenge is to organize it in TreeNode objects.

Can someone give a hint or an impossibility result for this?

Answer 1

If you want just two level trees, it's rather simple:

var roots = from root in data
where !data.Any(d => root.ParentID == d.ID)
select new TreeNode 
{
    Data = root,
    Children = data.Where(d => d.ParentID == root.ID).ToList(),
}

Answer 2

LINQ does not do particularly well with recursive data structures, but you can get close.

Since you probably want a tree of arbitrary depth, I'll change your definition of Children and add a constructor a helper method that will do the recursion needed to make a tree-building LINQ statement possible.

class TreeNode
{
    public DataObject Data { get; set; }
    public List<TreeNode> Children { get; private set; }

    public TreeNode(DataObject data)
    {
        Data = data;
        Children = new List<TreeNode>();
    }

    //name chosen to match XElement method.  I would name this
    //SelfAndDescendants or change the behavior to match the name.
    public IEnumerable<TreeNode> DescendantsAndSelf()
    {
        return (new TreeNode[] { this }).Concat(from c in this.Children
                                                from sc in c.DescendantsAndSelf()
                                                select sc);
    }
}

Now we can define the following method:

public static TreeNode BuildTree(IEnumerable<DataObject> items, int rootId)
{
    var root = new TreeNode(new DataObject(rootId, int.MinValue, "Root"));
    return (from i in items
            let n = new TreeNode(i)
            group n by n.Data.ParentID into nodeGroup
            orderby nodeGroup.Key ascending
            select nodeGroup)
            .Aggregate(root, (parent, childGroup) =>
            {
                parent.DescendantsAndSelf()
                      .First(n => n.Data.ID == childGroup.Key)
                      .Children.AddRange(childGroup);
                return parent; 
            });
}

This method makes some assumptions, but should get you in the right direction.

• None of the passed in elements are the root node of the tree and a root node will be created to be the return value.
• The id of the parent node is always lower than the id of the node (this lets OrderBy + Aggregate be called to push the items into the tree)
• Every item in the sequence passed to the method will belong to the root or one of the other items (otherwise an exception will be thrown by the .First() call).