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:
- 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.
- Second we need to configure the method to read “ID” property of the model.
- Third parameter configure the method to read “Parent ID” property of the model.
- Fourth parameter, defines which property of parent can be used to attach the child nodes.
- 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).
- 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.