Nice & universal way to convert List of items to Tree

I have list of categories:

╔════╦═════════════╦═════════════╗
║ Id ║ Name        ║ Parent_id   ║
╠════╬═════════════╬═════════════╣
║ 1  ║ Sports      ║ 0           ║
║ 2  ║ Balls       ║ 1           ║
║ 3  ║ Shoes       ║ 1           ║
║ 4  ║ Electronics ║ 0           ║
║ 5  ║ Cameras     ║ 4           ║
║ 6  ║ Lenses      ║ 5           ║
║ 7  ║ Tripod      ║ 5           ║
║ 8  ║ Computers   ║ 4           ║
║ 9  ║ Laptops     ║ 8           ║
║ 10 ║ Empty       ║ 0           ║
║ -1 ║ Broken      ║ 999         ║
╚════╩═════════════╩═════════════╝ 

Each category have a parent. When parent is 0 - that means it's the root category.

What is the nicest way to convert it to tree structure like below?

Sport
 ├ Balls
 └ Shoes

Electronics
 ├ Cameras
 │  ├ Lenses
 │  └ Tripod
 │
 └ Computers
    └ Laptops

Empty

In other words - how to bring data from this structure:

class category
{
    public int Id;
    public int ParentId;
    public string Name;
}

Into this one:

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

    public List<Category> Subcategories;
}

in universal way? // Universal means not only for mentioned class.

Do you have some smart ideas? ;)

Data:

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

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