12,446,296 members (55,090 online)
Add your own
alternative version

68.5K views
1.9K downloads
53 bookmarked
Posted

# Recursively Traversing a Hierarchical Data Structure Using LINQ

, 10 Apr 2010 CPOL
 Rate this:
Please Sign up or sign in to vote.
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

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 NullException on accessing the predicate Omer Tariq20-Jul-14 20:12 Omer Tariq 20-Jul-14 20:12
 How would you Delete an entry? Member 307227829-Nov-12 16:00 Member 3072278 29-Nov-12 16:00
 Re: How would you Delete an entry? Member 307227829-Nov-12 16:55 Member 3072278 29-Nov-12 16:55
 Yet another way! Nicholas Butler12-Apr-10 1:08 Nicholas Butler 12-Apr-10 1:08
 Re: Yet another way! deBUGer!31-Dec-14 2:03 deBUGer! 31-Dec-14 2:03
 My two cents... Philippe Bouteleux29-Mar-10 3:13 Philippe Bouteleux 29-Mar-10 3:13
 Another way... [modified] Paulo Zemek29-Mar-10 2:42 Paulo Zemek 29-Mar-10 2:42
 Re: Another way... Paul B.29-Mar-10 15:44 Paul B. 29-Mar-10 15:44
 Re: Another way... Richard Deeming30-Mar-10 5:05 Richard Deeming 30-Mar-10 5:05
 Re: Another way... Greg Cadmes9-Dec-10 11:03 Greg Cadmes 9-Dec-10 11:03
 Re: Another way... Richard Deeming10-Dec-10 1:54 Richard Deeming 10-Dec-10 1:54
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Aug-16 13:12 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.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160811.3 | Last Updated 10 Apr 2010
Article Copyright 2010 by Rajitha Wimalasooriya
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid