Ordering a list by depth level

Cyberboy1551 0
Viewed 49

I have a list of objects that look like this:

public class Test
{
    public int Id;
    public int Level; // The depth level of this node
    public int ParentId; // The id of the parent node (null for level 1)
}

Two Important things to note are: 1) there is a maximum of 5 levels and 2) There is no root node. Aka, there can be multiple level 1 nodes

The current orientation of the list is each level concatenated on top of each other:

  1. Level 1 Items
  2. Level 2 Items
  3. Level 3 Items
  4. ... etc

I need the list in a Pre-order binary tree format. So for each level, the next item would be it's child recursing down.

Sorry if this is confusing.

I already had a somewhat working prototype but it requires a manual search and loop 5! times and it became a massive function.

I'm hoping there is a recursive way to accomplish this. Thanks in advance.

data-structures linq list recursion c#
2 Answers

You can create a tree and traverse it, but first I would suggest changing your tree so that it can be efficiently traversed:

var dict = items.GroupBy(i => i.ParentId).ToDictionary(p => p.Key, p => p.ToList());

Then we can use a generic method to do the actual traversing:

public static IEnumerable<T> DepthFirst<T>(T self, Func<T, IEnumerable<T>> selector)
{
    var stack = new Stack<T>();
    stack.Push(self);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var child in selector(current))
        {
            stack.Push(child);
        }
    }
}

This is an iterative method that uses a explicit stack rather than the implicit stack for recursive methods. I tend to prefer this way since it is reusable for all kinds of tree representation.

Note that your model cannot have 'null' as the parent, since your values are not nullable. You also need a root to start the traversing, so lets just assume the root is the node with the smallest parent value, and that there is only one root:

var rootNode = dict[dict.Keys.Min()].Single();
var orderedItems = DepthFirst(rootNode, n => dict[n.Id])

Or say you have multiple roots with a known level:

var orderedItems = items.Where(i => i.Level == rootLevel)
     .SelectMany(r =>  DepthFirst(r, n => dict[n.Id]));

Note that I personally prefer the term "depth first" and "breadth first", since I think they are more descriptive than pre/post order.

JonasH0

Since you specifically mention recursion, I mocked up a sample method to do this.

You didn't say if you have the ability to change the Test class or not, so I assumed "no" and made this class to simplify the example:

public class TreeifiedTest : Test
{
    public TreeifiedTest(Test test)
    {
        Id = test.Id;
        Level = test.Level;
        ParentId = test.ParentId;
    }
    
    public List<TreeifiedTest> Children { get; set; }
}

Using that, I created a recursive method to "treeify" the list:

public List<TreeifiedTest> Treeify(List<Test> list, int? parentId = null, int level = 0)
{
    var items = list.Where(i => i.ParentId == parentId).Select(i => new TreeifiedTest(i)).ToList();
    items.ForEach(i =>
    {
        i.Level = level + 1;
        i.Children = Treeify(list, i.Id, i.Level);
    });
    
    return items;
}

You can take a look at it working in this Fiddle with a bonus recursive method to display the output lol.

Daevin0
Related