Click here to Skip to main content
15,868,016 members
Articles / Programming Languages / C#

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 106.7K   2.3K   53   13
Recursively traversing a hierarchical data structure using LINQ without flattening the hierarchy or using foreach loop

LinqHierarchicalTraverse.png

Introduction

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.

Background

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:

C#
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:

C#
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.

C#
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>.

C#
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.

C#
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.

Usage

Now we can use syntax like below to query the hierarchical collection.

C#
IEnumerable<Item> result = myItems.Traverse(i => i.Id == 25);
result = myItems.Traverse(i => i.Name.Contains("Child"));
result = myItems.Traverse(i => !i.IsVisible);

Limitations

The current implementation will not support cyclic data structures.

License

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


Written By
Software Developer (Senior)
Australia Australia
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionWhy not foreach? Pin
Sam Hobbs3-May-21 18:14
Sam Hobbs3-May-21 18:14 
What is wrong with foreach? Is this more efficient than foreach?
QuestionUpdate matching records Pin
Girish Mahida23-Jan-18 21:35
Girish Mahida23-Jan-18 21:35 
QuestionNullException on accessing the predicate Pin
Omer Tariq20-Jul-14 20:12
Omer Tariq20-Jul-14 20:12 
QuestionHow would you Delete an entry? Pin
Member 307227829-Nov-12 16:00
Member 307227829-Nov-12 16:00 
AnswerRe: How would you Delete an entry? Pin
Member 307227829-Nov-12 16:55
Member 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
deBUGer!31-Dec-14 2:03 
GeneralMy two cents... Pin
Philippe Bouteleux29-Mar-10 3:13
Philippe 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
Paul 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
Greg 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.