Nice & universal way to convert List of items to Tree

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

The top answers didn't meet my specific requirements, so I took a crack at it. I'm sure I've done this some times before, but this time it was fun to use generics and the ToLookup method. This goes through the source collection to get all the existing ids and build the lookup which essentially links all the children to their parents, then it is a simple matter of building the tree.

/// <summary>
/// Generate a tree from a flat list where items know their parents; may have multiple root (parentless) items
/// </summary>
///
/// <typeparam name="TSource">Type of the input source items</typeparam>
/// <typeparam name="TKey">Type of the id of items and their parents. This type has to have a default EqualityComparer{T}</typeparam>
/// <typeparam name="TElement">Type of the returned items. Does not need to be the same type as the items in the input source collection <typeparamref name="TSource"/></typeparam>
///
/// <param name="source">Flat collection of input items of type <typeparamref name="TSource"/></param>
/// <param name="elementKeySelector">Gets the unique key for this item</param>
/// <param name="parentKeySelector">Gets the non-null key of the parent item. If this key is not among the existing element keys it is a root item (parentless).</param>
/// <param name="elementSelector">Get the element from the source item which will be returned in the results</param>
/// <returns><cref>TreeNode</cref> with empty Element, all root (parentless) items as Children of this node</returns>
public static TreeNode<TElement> GenerateTree<TSource, TKey, TElement>(
    IReadOnlyCollection<TSource> source,
    Func<TSource, TKey> elementKeySelector,
    Func<TSource, TKey> parentKeySelector,
    Func<TSource, TElement> elementSelector)
{
    //// First get all existing item keys and create a lookup from parent key to child elements

    var allFoundKeys = source.Select(elementKeySelector).ToHashSet();

    var parent2ChildrenLookup = source.ToLookup(parentKeySelector);

    //// Second pass is to process all root nodes in the parent2ChildrenLookup which recursively processes all children of those nodes etc.

    var rootTreeNode = new TreeNode<TElement>() { Children = new List<TreeNode<TElement>>() };

    foreach (var grouping in parent2ChildrenLookup.Where(g => allFoundKeys.Contains(g.Key) == false))
    {
        // Start with parentless nodes, the rest will be collected in this call recursively.
        AddChildTreeNodes(rootTreeNode, grouping);
    }

    void AddChildTreeNodes(TreeNode<TElement> treeNode, IEnumerable<TSource> children)
    {
        foreach (var child in children)
        {
            var childNode = new TreeNode<TElement>()
            {
                Element = elementSelector(child),
                Children = new List<TreeNode<TElement>>(),
            };

            treeNode.Children.Add(childNode);

            //// Now handle children of this child node, if there are any.

            var childKey = elementKeySelector(child);

            if (parent2ChildrenLookup.Contains(childKey))
            {
                AddChildTreeNodes(childNode, parent2ChildrenLookup[childKey]);
            }
        }
    }

    return rootTreeNode;
}

Here is the tree node class

/// <summary>
/// Helper node for creating trees
/// </summary>
/// <typeparam name="T">Type of the element of interest</typeparam>
public class TreeNode<T>
{
    /// <summary>
    /// Gets or sets the element
    /// </summary>
    public T Element { get; set; }

    /// <summary>
    /// Gets or sets the collection of children of this node.
    /// </summary>
    public IList<TreeNode<T>> Children { get; set; }
}

The call is quite simple in this case

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

var tree = GenerateTree(
    categories,
    s => s.Id,
    s => s.ParentId,
    s => s.Name);

Answer 11

Following up on damian-drygiel's answer,

This approach is the same, but uses an action to apply the Subcategories property as a parameter, so you don't need a separate TreeItem<T> model.

So if you start with

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

    public List<category> Subcategories; //This is unpopulated
}

Then this will populate Subcategories and return the updated IEnumerable<category>

internal static class GenericHelpers
{
    
    public static IEnumerable<T> GenerateTree<T, K>(
        this IEnumerable<T> collection,
        Func<T, K> id_selector,
        Func<T, K> parent_id_selector,
        Action<T, IEnumerable<T>> childrenApplier,
        K root_id = default(K))
    {
        foreach (var c in collection.Where(c => EqualityComparer<K>.Default.Equals(parent_id_selector(c), root_id)))
        {
            var children = collection.GenerateTree<T,K>(id_selector, parent_id_selector, childrenApplier, id_selector(c));
            childrenApplier(c, children);
                
            yield return c;
        }
    }
}

Only difference here is the Action<T, IEnumerable<T>> childrenApplier parameter, which looks like (c, newItems) => c.Children = newItems when using the method.

Usage:

var collection = new List<category>();
collection.GenerateTree(c => c.Id, c => c.ParentId, (c, newItems) => c.Children = newItems); 

See here for an example fiddle https://dotnetfiddle.net/473uIK

Answer 12

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