c# - Depth-first flattened collection of an object hierarchy using LINQ

Question

I have an object hierarchy (MasterNode -> ChildNodes) where master and child nodes are of the same type, and there are only two levels (top level and children) like this ('A' is parent of D,E and F, 'B' is parent of G, etc)

A--+
|  D
|  E
|  F
|
B--+
|  G
|
C--+
   H
   I

Suppose I have a MasterNodes as an IEnumerable of the parent objects (A,B,C) and given a parent object X I can get an IEnumerable of its children by X.children

I know that I can enumerate all of the leaf (child nodes) with the SelectMany method or by using

from parent in Masternodes
from child in parent.children
select child

This will give me this sequence:

[D,E,F,G,H,I]

,but this is not what I am asking for.

What is the LINQ query to get a depth-first sequence of the objects in the MasterNodes collection? (return first parent then all of its children then next parent then all of its children etc etc)

The expected result should be a sequence like this:

[A,D,E,F,B,G,C,H,I]

UPDATE:

I am asking for pure .NET ready LINQ. I know that I can define my own methods to do things, but I want something that is based only on the framework provided methods.

Answer 1

If you have a class like below

public class Node
{
    public string Name;
    public List<Node> Children = new List<Node>();
}

your linq would be

 Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
 Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

Test Code:

Node[] roots = new Node[]{ new Node(){Name="A"},new Node(){Name="B"},new Node(){Name="C"} };
roots[0].Children.Add(new Node(){Name="D"});
roots[0].Children.Add(new Node(){Name="E"});
roots[0].Children.Add(new Node(){Name="F"});

roots[1].Children.Add(new Node(){Name="G"});

roots[2].Children.Add(new Node(){Name="H"});
roots[2].Children.Add(new Node(){Name="I"});

Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

var result = String.Join(",",Flatten(roots).Select(x=>x.Name));

Console.WriteLine(result);