Nice & universal way to convert List of items to Tree

Question

If you want to have universal method you''ll need an additional class:

public class TreeItem<T>
{
    public T Item { get; set; }
    public IEnumerable<TreeItem<T>> Children { get; set; }
}

Then use it with this helper:

internal static class GenericHelpers
{
    /// <summary>
    /// Generates tree of items from item list
    /// </summary>
    /// 
    /// <typeparam name="T">Type of item in collection</typeparam>
    /// <typeparam name="K">Type of parent_id</typeparam>
    /// 
    /// <param name="collection">Collection of items</param>
    /// <param name="id_selector">Function extracting item's id</param>
    /// <param name="parent_id_selector">Function extracting item's parent_id</param>
    /// <param name="root_id">Root element id</param>
    /// 
    /// <returns>Tree of items</returns>
    public static IEnumerable<TreeItem<T>> GenerateTree<T, K>(
        this IEnumerable<T> collection,
        Func<T, K> id_selector,
        Func<T, K> parent_id_selector,
        K root_id = default(K))
    {
        foreach (var c in collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), root_id)))
        {
            yield return new TreeItem<T>
            {
                Item = c,
                Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c))
            };
        }
    }
}

Usage:

var root = categories.GenerateTree(c => c.Id, c => c.ParentId);

Testing:

static void Test(IEnumerable<TreeItem<category>> categories, int deep = 0)
{
    foreach (var c in categories)
    {
        Console.WriteLine(new String('\t', deep) + c.Item.Name);
        Test(c.Children, deep + 1);
    }
}
// ...
Test(root);

Output

Sport
    Balls
    Shoes
Electronics
    Cameras
        Lenses  
        Tripod
    Computers
        Laptops
Empty

foreach (var cat in categories)
{
    cat.Subcategories = categories.Where(child => child.ParentId == cat.Id)
                                  .ToList();
}

You'll get O(n*n) complexity.

---

More optimized way is to use Lookup tables:

var childsHash = categories.ToLookup(cat => cat.ParentId);

foreach (var cat in categories)
{
    cat.Subcategories = childsHash[cat.Id].ToList();
}

Which gives you O(2*n) ≈ O(n)

As result, you'll have next structure (shown from LinqPad):

Yet another way with passing how to identify parent. Full code (including internal implementation of ITree and xUnit test) is available as Gist here: Nice & universal way to convert List of items to Tree

Usage:

ITree<Category> tree = categories.ToTree((parent, child) => child.ParentId == parent.Id);

Proiduces:

        <ROOT>
        -Sports
        --Balls
        --Shoes
        -Electronics
        --Cameras
        ---Lenses
        ---Tripod
        --Computers
        ---Laptops
        -Empty
        -Broken

Universal tree node interface:

public interface ITree<T>
{
    T Data { get; }
    ITree<T> Parent { get; }
    ICollection<ITree<T>> Children { get; }
    bool IsRoot { get; }
    bool IsLeaf { get; }
    int Level { get; }
}

Extension method for collection:

public static ITree<T> ToTree<T>(this IList<T> items, Func<T, T, bool> parentSelector)
{
    if (items == null) throw new ArgumentNullException(nameof(items));

    var lookup = items.ToLookup(
            item => items.FirstOrDefault(parent => parentSelector(parent, item)),
            child => child);

    return Tree<T>.FromLookup(lookup);
}

You can use below database query to get the list of categories with parent-child relations:

WITH tree (categoryId, parentId, level, categoryName, rn) as 
(
   SELECT categoryId, parentid, 0 as level, categoryName,

       convert(varchar(max),right(row_number() over (order by categoryId),10)) rn
   FROM Categories
   WHERE parentid = 0

   UNION ALL

   SELECT c2.categoryId, c2.parentid, tree.level + 1, c2.categoryName,

       rn + '/' + convert(varchar(max),right(row_number() over 
       (order by tree.categoryId),10))
   FROM Categories c2 

     INNER JOIN tree ON tree.categoryId = c2.parentid
)

SELECT *
FROM tree
order by RN

I hope this will help you out.

Here is a little example I whipped up. It's pretty "Generic".

One could also make a generic approach by defining an interface (which would then allow the function arguments to be simplified) - however, I chose not to do so. In any case, the "mapper" and selector functions allows this it work across distinct types.

Also note that this is not a very efficient implementation (as it keeps around all possible children for all subtrees and repeatedly iterates such), but may be suitable for the given task. In the past I have also used a Dictionary<key,collection> approach, which has better bounds, but I didn't feel like writing it that way :)

This runs as a "LINQPad C# Program". Enjoy!

// F - flat type
// H - hiearchial type
IEnumerable<H> MakeHierarchy<F,H>(
    // Remaining items to process
    IEnumerable<F> flat,
    // Current "parent" to look for
    object parentKey,
    // Find key for given F-type
    Func<F,object> key,
    // Convert between types
    Func<F,IEnumerable<H>,H> mapper,
    // Should this be added as immediate child?
    Func<F,object,bool> isImmediateChild) {

    var remainder = flat.Where(f => !isImmediateChild(f, parentKey))
        .ToList();

    return flat
        .Where(f => isImmediateChild(f, parentKey))
        .Select(f => {
            var children = MakeHierarchy(remainder, key(f), key, mapper, isImmediateChild);
            return mapper(f, children);
        });
}

class category1
{
    public int Id;
    public int ParentId;
    public string Name;

    public category1(int id, string name, int parentId) {
        Id = id;
        Name = name;
        ParentId = parentId;
    }
};

class category2
{
    public int Id;
    public int ParentId;
    public string Name;

    public IEnumerable<category2> Subcategories;
};

List<category1> categories = new List<category1>() {
    new category1(1, "Sport", 0),
    new category1(2, "Balls", 1),
    new category1(3, "Shoes", 1),
    new category1(4, "Electronics", 0),
    new category1(5, "Cameras", 4),
    new category1(6, "Lenses", 5),  
    new category1(7, "Tripod", 5), 
    new category1(8, "Computers", 4),
    new category1(9, "Laptops", 8),
    new category1(10, "Empty", 0),
    new category1(-1, "Broken", 999),
};

object KeyForCategory (category1 c1) {
    return c1.Id;
}

category2 MapCategories (category1 c1, IEnumerable<category2> subs) {
    return new category2 {
        Id = c1.Id,
        Name = c1.Name,
        ParentId = c1.ParentId,
        Subcategories = subs,
    };
}

bool IsImmediateChild (category1 c1, object id) {
    return c1.ParentId.Equals(id);
}

void Main()
{
    var h = MakeHierarchy<category1,category2>(categories, 0,
        // These make it "Generic". You can use lambdas or whatever;
        // here I am using method groups.
        KeyForCategory, MapCategories, IsImmediateChild);
    h.Dump();
}

Using Ilya Ivanov and Damian Drygiel solutions, I've written some code, that makes a tree with any collection and any levels of children, even if you exactly don't know, what nodes will be roots.

Tree node entry

public sealed class TreeNode<T, TKey>
{
    public T Item { get; set; }
    public TKey ParentId { get; set; }

    public IEnumerable<TreeNode<T, TKey>> Children { get; set; }
}

Extension methods

public static class EnumerableExtensions
{
    public static IEnumerable<TreeNode<T, TKey>> ToTree<T, TKey>(
        this IList<T> collection,
        Func<T, TKey> itemIdSelector,
        Func<T, TKey> parentIdSelector)
    {
        var rootNodes = new List<TreeNode<T, TKey>>();
        var collectionHash = collection.ToLookup(parentIdSelector);

        //find root nodes
        var parentIds = collection.Select(parentIdSelector);
        var itemIds = collection.Select(itemIdSelector);
        var rootIds = parentIds.Except(itemIds);

        foreach (var rootId in rootIds)
        {
            rootNodes.AddRange(
                GetTreeNodes(
                    itemIdSelector,
                    collectionHash,
                    rootId)
                );
        }

        return rootNodes;
    }

    private static IEnumerable<TreeNode<T, TKey>> GetTreeNodes<T, TKey>(
        Func<T, TKey> itemIdSelector,
        ILookup<TKey, T> collectionHash,
        TKey parentId)
    {
        return collectionHash[parentId].Select(collectionItem => new TreeNode<T, TKey>
        {
            ParentId = parentId,
            Item = collectionItem,
            Children = GetTreeNodes(
                itemIdSelector,
                collectionHash,
                itemIdSelector(collectionItem))
        });
    }
}

Example:

 //Test Item
 public class TestTreeItem
 {
     public int Id { get; set; }
     public int ParentId { get; set; }

     public string Name { get; set; }
 }

 //Usage
 var collection = new List<TestTreeItem>
 {
      new TestTreeItem {Id = 1, Name = "1", ParentId = 14},
      new TestTreeItem {Id = 2, Name = "2", ParentId = 0},
      new TestTreeItem {Id = 3, Name = "3", ParentId = 1},
      new TestTreeItem {Id = 4, Name = "4", ParentId = 1},
      new TestTreeItem {Id = 5, Name = "5", ParentId = 2},
      new TestTreeItem {Id = 6, Name = "6", ParentId = 2},
      new TestTreeItem {Id = 7, Name = "7", ParentId = 3},
      new TestTreeItem {Id = 8, Name = "8", ParentId = 3},
      new TestTreeItem {Id = 9, Name = "9", ParentId = 5},
      new TestTreeItem {Id = 10, Name = "10", ParentId = 7}
  };

  var tree = collection.ToTree(item => item.Id, item => item.ParentId);

I hope, it helps someone. Enjoy

There is more simpler solution:
No need to create new nodes objects in memory. We have already had objects in source list. Just correctly fill Children.
Node class that can be base for other logic units. Path looks like 1.1, 1.2.1, 2 etc.
Instead of Path and ParentPath you can use Id and ParentId accordingly

    public abstract class Node
    {
        public int Id { get; set; }
        public string Name { get; set; }
        public string Path { get; set; }
        public string ParentPath
        {
            get
            {
                var lastDotPosition = Path.LastIndexOf('.');
                return lastDotPosition == -1 ? null : Path.Substring(0, lastDotPosition );
            }
        }
        public IEnumerable<Node> Children { get; set; }
    }

Recursive extention method:

public static class TreeExtension
{
    public static IEnumerable<T> GenerateTree<T>(this IEnumerable<T> table, T rootNode) where T : Node
    {
        var organizationalNodes = table.ToList();
        var rootNodes = organizationalNodes.Where(node => node.ParentPath == rootNode?.Path).ToList();

        foreach (var node in rootNodes)
        {
            node.Children = organizationalNodes.GenerateTree(node);
        }

        return rootNodes;
    }
}

Usage:

public class RegionNode : Node
{
    public string timezone {get; set;}
}

Get table from database and generate tree:

var result = await _context.GetItemsAsync<RegionNode>();
return result.GenerateTree( null);