The Story of My Life

Diary of a noob programmer

Turn a List into a Hierarchy Structure of Same Type

Scenario

There are cases we have a list of items, and these items should get connected in a tree structure. In case those item declared an empty collection of children, this algorithm is one way to go.

Code

The following code is the helper i wrote.

/// <summary>
/// Links a collection of flat node in a hierarchy way and returns selected nodes
/// </summary>
/// <typeparam name="TSource">Type of node objects</typeparam>
/// <typeparam name="TParentId">Type of parent Id key</typeparam>
/// <param name="flatData">Collection of nodes that are not linked together</param>
/// <param name="idProperty">Select the ID property of the class</param>
/// <param name="parentIdProperty">Select the parent ID property of the class</param>
/// <param name="childrenProperty">Select children property of the class</param>
/// <param name="isRoot">If provided, check if a node is a root node, otherwise check if the parent ID is null</param>
/// <param name="filter">if provided, filter the desired nodes within that tree, otherwise return root nodes</param>
/// <returns>Returns a collection of selected nodes</returns>
private IEnumerable<TSource> ListToTree<TSource, TParentId>(
    IEnumerable<TSource> flatData,
    Expression<Func<TSource, TParentId>> idProperty,
    Expression<Func<TSource, TParentId>> parentIdProperty,
    Expression<Func<TSource, ICollection<TSource>>> childrenProperty,
    Func<TSource, bool> isRoot = null,
    Func<TSource, bool> filter = null)
{
    var idCompiled = idProperty.Compile();
    var parentIdCompiled = parentIdProperty.Compile();
    var childrenCompiled = childrenProperty.Compile();

    var lookup = new Dictionary<TParentId, TSource>();
    foreach (var item in flatData)
    {
        var nodeId = idCompiled(item);
        lookup.Add(nodeId, item);
    }

    foreach (var node in lookup)
    {
        var parentId = parentIdCompiled(node.Value);
        if (isRoot==null ? (parentId != null) : (!isRoot(node.Value)))
        {
            var found = lookup[parentId];
            var childrenRef = childrenCompiled(found);
            childrenRef.Add(node.Value);
        }
    }

    var result = lookup.Select(s => s.Value);
    if (filter != null)
    {
        result = result.Where(filter);
    }
    else
    {
        result = result.Where(w=> isRoot == null ? (parentIdCompiled(w) == null) : (isRoot(w)));
    }

    return result;
}

In case you have a collection of children, within the class definition, the code can be copied and work without any modification.

How To Use

The required parameters are as follow:

  1. First we need a list of data, and each of which should contains an ID, a Parent ID, and in the end, a collection of children.
  2. Second we need to configure the method to read “ID” property of the model.
  3. Third parameter configure the method to read “Parent ID” property of the model.
  4. Fourth parameter, defines which property of parent can be used to attach the child nodes.
  5. Fifth parameter is used, to tell the this method, which nodes are root nodes; by default nodes with parent ID of null, considered as root (Optional).
  6. Sixth parameter is used, to filter the desired nodes, within that tree; by default root nodes will return (Optional).

I used Lambda Expression for configurations of properties i mentioned above. using the sample Employee model (mentioned in “Sample Node Class” section).

So using model above, and with a list of data called result, we can call the ListToTree helper method.

var hierarchy = ListToTree(result, i=>i.Id, p => p.ParentId,c=>c.Managing );

As result this function will return a list of root nodes, which can be traversed through.

Sample Node Class

Here’s sample class of an employee that can manage other employees.

using System.Collections.Generic;

public partial class Employee : BaseEntity
    {
        public Favor( )
        {
            Managing = new HashSet<Employee>();
        }

        public int Id { get; set; }
        
        public string EmployeeName { get; set; }

        public int? ParentId { get; set; }


        public virtual ICollection<Employee> Managing { get; set; }
    }

 

Thank you for reading,
Hassan Faghihi.

Leave a Reply

Your email address will not be published. Required fields are marked *.

*
*
You may use these <abbr title="HyperText Markup Language">HTML</abbr> tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>