Linq - how to loop a tree data structure to build

Question

I have the following SQL table data:

The visual tree should look something like this:

To get the very top nodes I'm using:

var parentNodes = data
    .Where(i => i.AncestorId == i.DescedantId &&
                (data.Count(d => d.DescedantId == i.DescedantId) == 1))
    .ToList();

Any clue on how to build a function that would loop trough the structure and then build the tree style object?

My tree style object classes are:

public class ProfitCenterRoot
{
    public List<ProfitCenterItem> Data { get; set; }
}

public class ProfitCenterItem
{
    public int AncestorId { get; set; } 
    public int DescendantId { get; set; }
    public string Text { get; set; }
    public bool Leaf { get; set; }

    // These are the child items
    public List<ProfitCenterItem> Data { get; set; }
}

Answer 1

You can use recursion to add children to each parent. But first, I would add a default constructor to your classes to initialize the Data lists:

public class ProfitCenterRoot
{
    public List<ProfitCenterItem> Data { get; set; }

    public ProfitCenterRoot()
    {
        Data = new List<ProfitCenterItem>();
    }
}

public class ProfitCenterItem
{
    // Existing properties here

    public ProfitCenterItem()
    {
        Data = new List<ProfitCenterItem>();
    }
}

Then you can create a simple method that takes in a Parent and a list of all children, recursively add children to each child of the parent, and then add the children to the parent:

public static void AddChildren(ProfitCenterItem parent, 
    IEnumerable<ProfitCenterItem> allChildren )
{
    var children = allChildren
        .Where(child =>
               child.AncestorId == parent.DescendantId &&
               child.AncestorId != child.DescendantId)
        .ToList();

    foreach (var child in children)
    {
        AddChildren(child, allChildren.Except(children));
        parent.Data.Add(child);
    }
}

So to populate your objects, you could then do:

var parentNodes = data
    .Where(i => i.AncestorId == i.DescendantId &&
                (data.Count(d => d.DescendantId == i.DescendantId) == 1))
    .ToList();

var root = new ProfitCenterRoot();

foreach (var parentNode in parentNodes)
{
    AddChildren(parentNode, data.Except(parentNodes));
    root.Data.Add(parentNode);
}

Answer 2

I think I have an even easier way to build the tree.

First up though, it seems odd to have the properties AncestorId & DescendantId for each node, so I simplified the structure to just Id like this:

public class ProfitCenterItem
{
    public int Id { get; set; } 
    public List<ProfitCenterItem> Data { get; set; }
}

Now it becomes easy.

The nodes that are actually relevant are those where AncestorId != DescendantId so we get those:

var nonSelf =
    data
        .Where(x => x.AncestorId != x.DescendantId)
        .ToArray();

Now the parent nodes are simply those ids that appear on the left but don't appear on the right. Like this:

var parentNodes =
    Enumerable
        .Except(
            nonSelf.Select(x => x.AncestorId),
            nonSelf.Select(x => x.DescendantId));

Now to build the tree we create a lookup for the children:

var lookup = nonSelf.ToLookup(x => x.AncestorId, x => x.DescendantId);

Here's the trickiest part - a recursive build function for traversing the lookup to build all the nodes:

Func<int, ProfitCenterItem> build = null;
build = n =>
    new ProfitCenterItem()
    {
        Id = n,
        Data = lookup[n].Select(x => build(x)).ToList()
    };

Finally we just need to create the root node and call build to create the parent nodes:

var root = new ProfitCenterRoot()
{
    Data = parentNodes.Select(x => build(x)).ToList()
};

Here's the result I get: