Click here to Skip to main content
15,038,345 members
Articles / Programming Languages / C#
Posted 27 Mar 2010


53 bookmarked

Recursively Traversing a Hierarchical Data Structure Using LINQ

Rate me:
Please Sign up or sign in to vote.
4.47/5 (8 votes)
10 Apr 2010CPOL2 min read
Recursively traversing a hierarchical data structure using LINQ without flattening the hierarchy or using foreach loop



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.

Y Combinator

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 Extensions class.

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 IEnumerable<Item>.

var traverse = Extensions.Y<IEnumerable<Item>, IEnumerable<Item>>(...)

Extension Method

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

    return traverse(source);

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.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Rajitha Wimalasooriya
Software Developer (Senior)
Australia Australia
No Biography provided

Comments and Discussions

QuestionWhy not foreach? Pin
Sam Hobbs3-May-21 18:14
MemberSam Hobbs3-May-21 18:14 
QuestionUpdate matching records Pin
Girish Mahida23-Jan-18 21:35
MemberGirish Mahida23-Jan-18 21:35 
QuestionNullException on accessing the predicate Pin
Omer Tariq20-Jul-14 20:12
MemberOmer Tariq20-Jul-14 20:12 
QuestionHow would you Delete an entry? Pin
Member 307227829-Nov-12 16:00
MemberMember 307227829-Nov-12 16:00 
AnswerRe: How would you Delete an entry? Pin
Member 307227829-Nov-12 16:55
MemberMember 307227829-Nov-12 16:55 
GeneralYet another way! Pin
Nicholas Butler12-Apr-10 1:08
sitebuilderNicholas Butler12-Apr-10 1:08 
GeneralRe: Yet another way! Pin
deBUGer!31-Dec-14 2:03
MemberdeBUGer!31-Dec-14 2:03 
GeneralMy two cents... Pin
Philippe Bouteleux29-Mar-10 3:13
MemberPhilippe Bouteleux29-Mar-10 3:13 
GeneralAnother way... [modified] PinPopular
Paulo Zemek29-Mar-10 2:42
mvaPaulo Zemek29-Mar-10 2:42 
GeneralRe: Another way... Pin
Paul B.29-Mar-10 15:44
MemberPaul B.29-Mar-10 15:44 
GeneralRe: Another way... Pin
Richard Deeming30-Mar-10 5:05
mveRichard Deeming30-Mar-10 5:05 
QuestionRe: Another way... Pin
Greg Cadmes9-Dec-10 11:03
MemberGreg Cadmes9-Dec-10 11:03 
AnswerRe: Another way... Pin
Richard Deeming10-Dec-10 1:54
mveRichard Deeming10-Dec-10 1:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.