using System;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        FirstTest();

        SecondTest();

    }

    public static void FirstTest()

    {

        var categories = new List<Category>() {

            new Category(3, "Shoes", 1),

            new Category(5, "Cameras", 4),

            new Category(6, "Lenses", 5),

            new Category(2, "Balls", 1),

            new Category(3, "Shoes", 1),

            new Category(0, "Root", -1),

            new Category(4, "Electronics", 0),

            new Category(8, "Computers", 4),

            new Category(1, "Sport", 0),

            new Category(9, "Laptops", 8),

            new Category(10, "Empty", 0),

            new Category(-1, "Broken", 999),

        };

        Console.WriteLine("First Example, @Damian Drygiel's answer:");

        var tree1 = GenerateTreeWithRecursion<Category, int>(categories, r => r.Id, r => r.ParentId, -1); // -1 in this example is the required root id

        PrintTree(tree1.Single());

        Console.WriteLine();

        Console.WriteLine("First Example, @Ilya Ivanov's answer:");

        var tree2 = GenerateTreeWithLookup<Category, int>(categories, r => r.Id, r => r.ParentId, -1);   // -1 in this example is the required root id

        PrintTree(tree2);

        Console.WriteLine();

    }

    public static void SecondTest()

    {

        var a = new Node<string>("a", null);

        var a1 = new Node<string>("a1", a);

        var a2 = new Node<string>("a2", a);

        var b11 = new Node<string>("b11", a1);

        var b12 = new Node<string>("b12", a1);

        var b21 = new Node<string>("b21", a2);

        var b22 = new Node<string>("b22", a2);

        var unorderedList = new List<Node<string>>{a2, a1, a, b21, b12, b11, b22};

        Console.WriteLine("Second Example, @Damian Drygiel's answer:");

        var tree1 = GenerateTreeWithRecursion<Node<string>, string>(unorderedList, r => r.Id, r => r.GetParentId(), a.GetParentId()); // a.GetParentId() is null, which in this example is the required root id

        PrintTree(tree1.Single());

        Console.WriteLine();

        Console.WriteLine("Second Example, @Ilya Ivanov's answer:");

        var tree2 = GenerateTreeWithLookup<Node<string>, string>(unorderedList, r => r.Id, r => r.GetParentId(), a.GetParentId());   // a.GetParentId() is null, which in this example is the required root id

        PrintTree(tree2);

        Console.WriteLine();

    }

    // @Damian Drygiel answer

    public static IEnumerable<TreeItem<T>> GenerateTreeWithRecursion<T, K>(

        IEnumerable<T> collection,

        Func<T, K> id_selector,

        Func<T, K> parent_id_selector,

        K id_to_match)

    {

        var tree = new List<TreeItem<T>>();

        var nodesWithMatchedId = collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), id_to_match)).ToList();

        foreach (var c in nodesWithMatchedId)

        {

            tree.Add(new TreeItem<T>

            {

                Item = c,

                Children = GenerateTreeWithRecursion(collection, id_selector, parent_id_selector, id_selector(c))

            });

        }

        return tree;

    }

    //@Ilya Ivanov answer

    public static TreeItem<T> GenerateTreeWithLookup<T, K>(

        IEnumerable<T> collection,

        Func<T, K> id_selector,

        Func<T, K> parent_id_selector,

        K root_id)

    {

        var tree = collection.Select(r => new TreeItem<T> { Item = r, Children = new List<TreeItem<T>>() }).ToList();

        var lookup = tree.ToLookup(node => parent_id_selector(node.Item));

        foreach (var node in tree)

        {

            node.Children = lookup[id_selector(node.Item)].ToList();

        }

        return tree.First(node => EqualityComparer<K>.Default.Equals(parent_id_selector(node.Item), root_id));

    }

​

    static void PrintTree<T>(TreeItem<T> root, int deep = 0)

    {

        Console.WriteLine(new String('\t', deep) + root.Item.ToString());

        foreach (var c in root.Children)

        {

            PrintTree(c, deep + 1);

        }

    }

}

​

public class TreeItem<T>

{

    public T Item { get; set; }

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

}

​

​

#region test classes

​

#region first test class

public class Category

{

    public int Id;

    public int ParentId;

    public string Name;

    public Category(int id, string name, int parentId)

    {

        Id = id;

        Name = name;

        ParentId = parentId;

    }

    public override string ToString()

    {

        return Name;

    }

}

​

#endregion first test class

​

#region second test class

public class Node<T>

{

    public T Id { get; set; }

    public Node<T> Parent { get; set; }

    public Node(T id, Node<T> parent)

    {

        Id = id;

        Parent = parent;

    }

    public T GetParentId()

    {

        T id = default(T);

        if (Parent != null)

        {

            id = Parent.Id;

        }

        return id;

    }

    public override string ToString()

    {

        return Id.ToString();

    }

}

#endregion second test class

#endregion test classes

​