13,836,240 members
Add your own
alternative version

#### Stats

88.9K views
2.1K downloads
53 bookmarked
Posted 27 Mar 2010
Licenced CPOL

# Recursively Traversing a Hierarchical Data Structure Using LINQ

, 10 Apr 2010
Recursively traversing a hierarchical data structure using LINQ without flattening the hierarchy or using foreach loop

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

`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.

## Usage

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

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

## About the Author

 Software Developer (Senior) Australia
No Biography provided

 Pro

## Comments and Discussions

 First Prev Next
 Update matching records Girish Mahida23-Jan-18 22:35 Girish Mahida 23-Jan-18 22:35
 NullException on accessing the predicate Omer Tariq20-Jul-14 21:12 Omer Tariq 20-Jul-14 21:12
 How would you Delete an entry? Member 307227829-Nov-12 17:00 Member 3072278 29-Nov-12 17:00
 Re: How would you Delete an entry? Member 307227829-Nov-12 17:55 Member 3072278 29-Nov-12 17:55
 Yet another way! Nicholas Butler12-Apr-10 2:08 Nicholas Butler 12-Apr-10 2:08
 Re: Yet another way! deBUGer!31-Dec-14 3:03 deBUGer! 31-Dec-14 3:03
 My two cents... Philippe Bouteleux29-Mar-10 4:13 Philippe Bouteleux 29-Mar-10 4:13
 Another way... [modified] Paulo Zemek29-Mar-10 3:42 Paulo Zemek 29-Mar-10 3:42
 Re: Another way... Paul B.29-Mar-10 16:44 Paul B. 29-Mar-10 16:44
 Re: Another way... Richard Deeming30-Mar-10 6:05 Richard Deeming 30-Mar-10 6:05
 Re: Another way... Greg Cadmes9-Dec-10 12:03 Greg Cadmes 9-Dec-10 12:03
 Re: Another way... Richard Deeming10-Dec-10 2:54 Richard Deeming 10-Dec-10 2:54
 Last Visit: 23-Jan-19 5:22     Last Update: 23-Jan-19 5:22 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01 | 2.8.190114.1 | Last Updated 10 Apr 2010
Article Copyright 2010 by Rajitha Wimalasooriya
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid