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

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

using Ilya Ivanov algorithm (see above), i made the method more generic.

public static IEnumerable<TJ> GenerateTree<T, TK, TJ>(this IEnumerable<T> items,
                                                      Func<T, TK> idSelector,
                                                      Func<T, TK> parentSelector,
                                                      Func<T, IEnumerable<T>, TJ> outSelector)
{
       IList<T> mlist = items.ToList();

       ILookup<TK, T> mcl = mlist.ToLookup(parentSelector);

       return mlist.Select(cat => outSelector(cat, mcl[idSelector(cat)]));
}

usage :

IEnumerable<Category> mlc = GenerateTree(categories,
                                         c => c.Id, 
                                         c => c.ParentId,
                                         (c, ci) => new Category
                                         {
                                              Id = c.Id,
                                              Name = c.Name,
                                              ParentId = c.ParentId ,
                                              Subcategories = ci
                                         });

I perfer used interface than create new generic tree type. So I will change Damian Drygiel answer to this code:

public interface ITreeItem<T>
{
    IEnumerable<T> Children { get; set; }
}

public static IEnumerable<T> GenerateTree<T, K>(
    this IEnumerable<T> collection,
    Func<T, K> id_selector,
    Func<T, K> parent_id_selector,
    K root_id = default(K)) where T :ITreeItem<T>
{
    foreach (var c in collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), root_id)))
    {
        c.Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c));
        yield return c;
    }
}

and category will be like this:

class category :ITree<category>
{
  public int Id;
  public int ParentId;
  public string Name;
  public IEnumerable<category> Children;
}

You View Model Of Data:

public class PricesViewModel
{        
    public List<PriceType> PriceTypes { get; set; }// List OF Items with Parent ID
    public static string Data { get; set; } = ""; // Printed Items
    public static List<int> IDs { get; set; }// IDs of Your List To filters

    public static void Print(List<PriceType> categories, int deep = 0)
    {
        foreach (var c in categories)
        {
            if (PricesViewModel.IDs.Count(x => x == c.ID) > 0)// if Item not taken
            {
                for (int i = 0; i < deep; i++)// Get Spasece 
                {
                    PricesViewModel.Data += "&emsp;";
                    //Console.Wirte("    ");
                }
                PricesViewModel.Data +=  "<p>" +c.Name + "</p>"; //Save Items to Print
                //Console.WirteLine(c.Name);
                if (PricesViewModel.IDs.Count(x => x == c.ID) != 0)
                {
                    PricesViewModel.IDs.Remove(c.ID);//Filter Of IDs List
                    if (c.PriceTypes.Count != 0)
                        Print(c.PriceTypes.ToList(), deep + 1);
                }
            }
        }
    }
}

To Test Your Code:

PricesViewModel obj = new PricesViewModel();
obj.PriceTypes = db.PriceTypes.Include(x => x.PriceTypes).Include(x => x.priceType).Include(x => x.Prices).ToList();//GenerateTree(c => c.ID, c => c.TypeID);

PricesViewModel.IDs = obj.PriceTypes.Select(x=>x.ID).ToList();
PricesViewModel.Data = "";
PricesViewModel.Print(obj.PriceTypes);