Click here to Skip to main content
Click here to Skip to main content
Go to top

Recursively Traversing a Hierarchical Data Structure Using LINQ

, 10 Apr 2010
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

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:

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)

Share

About the Author

Rajitha Wimalasooriya
Software Developer
Australia Australia
No Biography provided

Comments and Discussions

 
QuestionNullException on accessing the predicate PinmemberOmer Tariq20-Jul-14 20:12 
QuestionHow would you Delete an entry? PinmemberMember 307227829-Nov-12 16:00 
AnswerRe: How would you Delete an entry? PinmemberMember 307227829-Nov-12 16:55 
GeneralYet another way! PinmentorNicholas Butler12-Apr-10 1:08 
GeneralMy two cents... PinmemberPhilippe Bouteleux29-Mar-10 3:13 
GeneralAnother way... [modified] PinmemberPaulo Zemek29-Mar-10 2:42 
GeneralRe: Another way... PinmemberPaul B.29-Mar-10 15:44 
GeneralRe: Another way... PinmemberRichard Deeming30-Mar-10 5:05 
QuestionRe: Another way... PinmemberGreg Cadmes9-Dec-10 11:03 
AnswerRe: Another way... PinmemberRichard Deeming10-Dec-10 1:54 

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

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

| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 10 Apr 2010
Article Copyright 2010 by Rajitha Wimalasooriya
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid