LINQ Traverse Upwards and Retrieve Parent Child Relationship

Question

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?

You need to show your own ideas first. This question is too open. For one, it matters much which kind of LINQ we're talking about. Just in-memory? — Gert Arnold, Jan 12 '16 at 11:09
Hello, what about performance? This kind of task should be solved using specific SGBD technology (ex: SQL Server offers CTE, you can go recursivelly to get your list of all elements that are part of your subtree ;)). Then you could "build" your tree in memory in O ( N ) time using some hashing collections. — George Lica, Jan 12 '16 at 12:52
It's not quite clear what is the question. You start with single `MyObject` and a child (direct or indirect) ID and need to find that child, or start with `List` etc. Also once you have `Children` property fro top down navigation, why don't you have a `Parent` property for easy bottom up navigation. — Ivan Stoev, Jan 12 '16 at 13:40

Enigmativity · Accepted Answer · 2016-01-12T22:45:58.057

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:

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

Thats great, so where you root in the code above if I have a List which is essence multiple parent nodes containing an infinite number of children how would that affect the code you have provided? — Csharper, Jan 12 '16 at 15:15
@YuraZaletskyy - I assume you mean the image? It's a screenshot taken from the output from [LINQPad](http://www.linqpad.com). I do most of my coding in that environment now. — Enigmativity, Jan 12 '16 at 22:47
That's just awesome, thank you. Although only a small problem your solution has taught me several things thank you! — Csharper, Jan 13 '16 at 08:17

score 0 · Answer 2 · answered Jan 12 '16 at 10:48

0

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

answered Jan 12 '16 at 10:48

Mike Jerred

9,551
5
22
42

sorry it's me. You're not traversing upwards from a given node up to root (my understanding of question) but just up to its direct parent. – Adriano Repetti Jan 12 '16 at 11:12
Ah, I have interpreted it as meaning he wants the parents with a relationship to this child, given that he already has the root. The question is not well phrased as it's actually impossible to traverse upwards as there are no links to the parent, only to the parent ID.I think some clarification from the OP is needed. – Mike Jerred Jan 12 '16 at 11:19

score 0 · Answer 3 · edited May 23 '17 at 11:58

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.

LINQ Traverse Upwards and Retrieve Parent Child Relationship

3 Answers3