CODEWITHSUNDEEP
linqc#-4.0
Csharper
Csharper

Reputation: 53

LINQ Traverse Upwards and Retrieve Parent Child Relationship

I have a tree structure which is in the following format:

public class MyObject
{
   public Guid ID { get; set; }

   public Guid ParentID { get; set; }

   public string Name { get; set; }

   private List<MyObject> MyChildren { get; set; }
}

If I have the ID of deeply nested Child within the children of MyObject I need to traverse upwards and get the Parent > Child relationship in a tree structure using LINQ preferably.

Any Ideas?

Upvotes: 0

Views: 2583

Answers (3)

Enigmativity
Enigmativity

Reputation: 117064

This works for me:

Func<MyObject, IEnumerable<MyObject>> flatten = null;
flatten = mo =>
    new [] { mo }
        .Concat(mo.MyChildren.SelectMany(x => flatten(x)));

var map = flatten(root).ToDictionary(x => x.ID);

Func<int, IEnumerable<MyObject>> getAncestorPath = null;
getAncestorPath = g =>
    map.ContainsKey(g)
    ? new [] { map[g] }.Concat(getAncestorPath(map[g].ParentID))
    : Enumerable.Empty<MyObject>();

To make this work I have to change the List<MyObject> MyChildren { get; set; } property to public. If you don't do this we need to know of some other way to get a list of MyObject so that we don't have to traverse the tree.

So, if I start with this object tree:

var root = new MyObject()
{
    ID = 1,
    ParentID = 0,
    MyChildren = new List<MyObject>()
    {
        new MyObject()
        {
            ID = 2,
            ParentID = 1,
            MyChildren = new List<MyObject>()
            {
            },
        },
        new MyObject()
        {
            ID = 3,
            ParentID = 1,
            MyChildren = new List<MyObject>()
            {
                new MyObject()
                {
                    ID = 4,
                    ParentID = 3,
                    MyChildren = new List<MyObject>()
                    {
                    },
                }
            },
        }
    },
};

And I ask for getAncestorPath(4) then I get this result:

result

Or, if I show it as a series of ids using String.Join(", ", getAncestorPath(someId).Select(x => x.ID)) then I get this:

4, 3, 1

If you have a list of roots, rather than a single root, then the code changes like so:

var map = roots.SelectMany(root => flatten(root)).ToDictionary(x => x.ID);

Upvotes: 2

George Lica
George Lica

Reputation: 1816

if your tree gets rarely mutated, for performance purposes I would "save" two additional fields: a "Left" and a "Right" field. Use the algorithm described here:

http://www.sitepoint.com/hierarchical-data-database-2/

for inspiration. The ideea is simple: You want to get in just one database call all your tree from database and also build it in O ( n) time in memory. If you feel so, you can keep the "ParentID" field and use it for building the in-memory graph. The downside is that rebuilding the tree costs you O ( N ) time (you must recompute the Left and Right values when a node gets inserted / removed or moved in another place in the tree). Otherwise I would use database specific technologies (CTE's)

Example: CTE Recursion to get tree hierarchy

Let's pay attention on performance also!!! it is very important.

Upvotes: 0

Mike Jerred
Mike Jerred

Reputation: 10525

private IEnumerable<MyObject> Flatten(IEnumerable<MyObject> objs)
{
    return objs.SelectMany(_ => Flatten(_.MyChildren));
}


var childId = 1234;
MyObject treeRoot = ...;
var flatObjects = Flatten(new [] { treeRoot });
var parents = flatObjects.Where(_ => _.MyChildren.Any(child => child.ID == childId));

Upvotes: 0

Related Questions