This article makes an attempt to show how to query for objects in a tree like hierarchical data structure using LINQ and without additional overhead of flattening the data structure or looping through the elements.
Unfortunately at the time of writing this article, there has not been a recursive query operator defined for LINQ. Therefore there is no direct method to query for objects in a hierarchical data structure as you would do for a flat object collection.
For querying a flat object collection, you would probably write something like:
myItems.FindAll(i => i.Id == 25)
For a hierarchical collection, wouldn't it be cool if we were able to write something similar to query for objects anywhere in the hierarchy:
myItems.Traverse(i => i.Id == 25)
This can be achieved by writing an extension method which internally uses the Y Combinator to recursively traverse the hierarchy.
The Y Combinator method can be used for writing recursive lambda expressions. More theoretical information and applications of the Y Combinator in C# can be found in the following excellent MSDN articles.
A generic implementation of the Y Combinator is used in the
public static class Extensions
private delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);
private static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
Recursive<A, R> rec = r => a => f(r(r))(a); return rec(rec);
For our purpose, we will be calling it with parameters of type
IEnumerable<Item>. Therefore the Y Combinator will ultimately return a delegate which takes an
IEnumerable<Item> as an parameter and returns an
var traverse = Extensions.Y<IEnumerable<Item>, IEnumerable<Item>>(...)
Traverse is an extension method for
IEnumerable<Item> which takes a predicate of type
Func<Item, bool> as a parameter. This parameter will contain the lambda expression encapsulating the selection logic for the items in the hierarchy.
public static IEnumerable<Item> Traverse(this IEnumerable<Item> source,
Func<Item, bool> predicate)
var traverse = Extensions.Y<IEnumerable<Item>, IEnumerable<Item>>(
f => items =>
var r = new List<Item>(items.Where(predicate));
r.AddRange(items.SelectMany(i => f(i.Children)));
Using the predicate, within the
Traverse extension method, we will build the recursive lambda expression to be passed over to the Y Combinator.
Now we can use syntax like below to query the hierarchical collection.
IEnumerable<Item> result = myItems.Traverse(i => i.Id == 25);
result = myItems.Traverse(i => i.Name.Contains("Child"));
result = myItems.Traverse(i => !i.IsVisible);
The current implementation will not support cyclic data structures.