Nice & universal way to convert List of items to Tree

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

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.

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);
}

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):