Creating a tree from a collection List<T>

Question

In order to create a tree, I use the following code.

var db = _context.GetContext();
        var accounts = await db
            .Set<TradingAccount>()
            .ToListAsync(cancellationToken: token);

        accounts.ForEach(
            account => account.Children = accounts.Where(
                child => child.ParentTradingAccountId == account.Id).ToList()
        );

        
        return accounts;

It works well (albeit not fast), but it does not create a completely correct tree. The same element can be both root and dependent. How can I exclude elements from the selection that have already been included in the tree?

Answer 1

The problem is that the code above adds dependent nodes as children, but does not remove them from the top-level list. Ususally recursion can be used to create tree structures, like so:

private IEnumerable<TracingAccount> GetAccounts(IEnumerable<TradingAccount> allAccounts, int parentTrackingAccountId)
{
  var accounts = allAccounts
    .Where(x => x.ParentTrackingAccountId == parentTrackingAccountId)
    .ToList();
  foreach (var acc in accounts)
  {
    // Get children of current node
    acc.Children = GetAccounts(allAccounts, acc.Id);
  }
  return accounts;
}

Above function retrieves all accounts for a specified parent id and calls itself again (that's why it is called a recursive function) to retrieve the children.

You can use the function in your code as follows (I assume that the root level accounts have a parent id of 0):

var db = _context.GetContext();
var allAccounts = await db
  .Set<TradingAccount>()
  .ToListAsync(cancellationToken: token);
var accounts = GetAccounts(allAccounts, 0);
return accounts;

The call to GetAccounts gets all root level accounts and - because the function calls itself again for each account - by that also retrieves the subtree of the root level accounts.

Answer 2

I wrote an algoritm to build a tree from a flat list. (a faster approach than filtering the same list over and over) As the items comes from a database, the parentId's should exists, and circular references should not occur. This example isn't able to handle those. But it might give you a jump-start how to make a faster algoritm.

In a nutshell, loop until all items are added. Use a while-loop instead of a foreach. The problem with foreach is that you aren't allowed to make modifications to the collection while iterating. This can be solved by creating copies, but it will end-up in many copy actions.

When it is a child (so the parentId is filled), I use the lookup dictionary to check if his parent was already added. If not, I'll skip it and check the next item. (this makes it possible that the parent is below the child in de list). When it is added to the parent, also add the child to the lookup, so their children are able to add them as child.

When it is a parent, I add it to the rootNodes, and add it to the lookup.

Multiple rootnodes are supported.

public static class TreeBuilder
{
    public static IEnumerable<Node> BuildTree(IEnumerable<Item> items)
    {
        var nodeLookup = new Dictionary<int, Node>();
        var rootNodes = new List<Node>();
        var itemCopy = items.ToList(); // we don't want to modify the original collection, make one working copy.
        int index = 0;

        while (true)
        {
            // when the item copy is empty, we're done.
            if (itemCopy.Count == 0)
                return rootNodes.ToArray();

            // do go out of bounds.
            index = index % itemCopy.Count;

            // get the current item on that index.
            var current = itemCopy[index];
            
            // does it have a parent?
            if(current.ParentId.HasValue)
            {
                // yes, so, it's a child
                // look if the parent is already found in the lookup.
                if (nodeLookup.TryGetValue(current.ParentId.Value, out var parentNode))
                {
                    // create a new node
                    var node = new Node { Id = current.Id };
                    // add it to the lookup
                    nodeLookup.Add(current.Id, node);
                    // add it as child node to the parent.
                    parentNode.ChildNodes.Add(node);
                    // remove it from the itemCopy (so don't check it again)
                    itemCopy.RemoveAt(index);

                    // The index doesn't need to be increase, because the current items is removed.
                }
                else
                    // next item, the parent is not in the tree yet.
                    index++;

            }
            else
            {
                // root node
                var node = new Node { Id = current.Id };
                nodeLookup.Add(current.Id, node);
                rootNodes.Add(node);
                itemCopy.RemoveAt(index);
            }
        }
    }
}

---

My test setup:

private void button4_Click(object sender, EventArgs e)
{
    /* 
        * 1
        * |
        * +- 2
        *    |
        *    +- 3
        *    |
        *    +- 5
        *       |
        *       +- 4
        */


    var items = new[]
    {
        new Item{ Id = 1, ParentId = null},
        new Item{ Id = 2, ParentId = 1},
        new Item{ Id = 3, ParentId = 2},
        new Item{ Id = 4, ParentId = 5},
        new Item{ Id = 5, ParentId = 2},
    };



    var tree = TreeBuilder.BuildTree(items);

    DisplayTree(tree);
}

private void DisplayTree(IEnumerable<Node> nodes, string indent = "")
{
    foreach (var node in nodes)
    {
        Trace.WriteLine($"{indent}{node.Id}");
        DisplayTree(node.ChildNodes, indent + "  ");
    }
}

The classes I used are:

public class Node
{
    public int Id { get; set; }
    public List<Node> ChildNodes { get; } = new List<Node>();

}

public class Item
{
    public int Id { get; set; }
    public int? ParentId { get; set; }
}

Which results in:

1
  2
    3
    5
      4