15

Let's take this n-tier deep structure for example:

public class SomeItem 
{
     public Guid ID { get;set; }
     public string Name { get; set; }
     public bool HasChildren { get;set; }
     public IEnumerable<SomeItem> Children { get; set; }
}

If I am looking to get a particular Item by ID (anywhere in the structure) is there some LINQ goodness I can use to easily get it in a single statement or do I have to use some recursive function as below:

   private SomeItem GetSomeItem(IEnumerable<SomeItem> items, Guid ID)
    {
        foreach (var item in items)
        {
            if (item.ID == ID)
            {
                return item;
            }
            else if (item.HasChildren)
            {
                return GetSomeItem(item.Children, ID);
            }
        }
        return null;
    }
Improve this question
3
  • Do you really need the HasChildren property? Commented Jan 27, 2011 at 8:50
  • Not really, just a helper so it reads better :) - Children.Count > 0 Commented Jan 27, 2011 at 8:54
  • 2
    @The_Butcher Children.Any() :) Commented Apr 24, 2015 at 17:39

5 Answers 5

Reset to default
35

LINQ doesn't really "do" recursion nicely. Your solution seems appropriate - although I'm not sure HasChildren is really required... why not just use an empty list for an item with no children?

An alternative is to write a DescendantsAndSelf method which will return all of the descendants (including the item itself), something like this;

// Warning: potentially expensive!
public IEnumerable<SomeItem> DescendantsAndSelf()
{
    yield return this;
    foreach (var item in Children.SelectMany(x => x.DescendantsAndSelf()))
    {
        yield return item;
    }
}

However, if the tree is deep that ends up being very inefficient because each item needs to "pass through" all the iterators of its ancestry. Wes Dyer has blogged about this, showing a more efficient implementation.

Anyway, if you have a method like this (however it's implemented) you can just use a normal "where" clause to find an item (or First/FirstOrDefault etc).

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Isn't the number of iterators generated a function of the total number of nodes rather than of the tree depth? (DescendantsAndSelf is called for each node).
If you repeatedly call DescendantsAndSelf() will it enumerate through the whole tree again or does LINQ keep the result?
@The_Butcher: LINQ doesn't do anything magical here. It's not going to cache anything for you. Of course, you could call ToList to generate a cached copy yourself.
@Amnon: True, the number of iterators generated is based on the number of nodes - but the number of iterators each item needs to pass through while it's being propagated to the top iterator depends on the depth of the tree. So a deep tree will still be less efficient to iterate over than a shallow one. Will edit to make that clearer.
I was about to ask a new question about recursive linq and that answer(the DescendantsAndSelf trick) is great.(combined with SelectMany). thanks. Can this be written as Extension method ?
|
5

Here's one without recursion. This avoids the cost of passing through several layers of iterators, so I think it's about as efficient as they come.

    public static IEnumerable<T> IterateTree<T>(this T root, Func<T, IEnumerable<T>> childrenF)
    {
        var q = new List<T>() { root };
        while (q.Any())
        {
            var c = q[0];
            q.RemoveAt(0);
            q.AddRange(childrenF(c) ?? Enumerable.Empty<T>());
            yield return c;
        }
    }

Invoke like so:

            var subtree = root.IterateTree(x => x. Children).ToList();
Improve this answer

1 Comment

Maybe it should be clearer if you implemented the function using a Queue instead of a List. The var c = q[0]; q.RemoveAt(0); is really a potentially more inefficient implementation of the Queue.Dequeue() method
3

hope this helps

public static IEnumerable<Control> GetAllChildControls(this Control parent)
{
  foreach (Control child in parent.Controls)
  {
    yield return child;

    if (child.HasChildren)
    {
      foreach (Control grandChild in child.GetAllChildControls())
        yield return grandChild;
    }
  }
}
Improve this answer

1 Comment

thanks - similar to mutable.net/blog/archive/2008/05/23/…
2

It is important to remember you don't need to do everything with LINQ, or default to recursion. There are interesting options when you use data structures. The following is a simple flattening function in case anyone is interested.

    public static IEnumerable<SomeItem> Flatten(IEnumerable<SomeItem> items)
    {
        if (items == null || items.Count() == 0) return new List<SomeItem>();

        var result = new List<SomeItem>();
        var q = new Queue<SomeItem>(collection: items);

        while (q.Count > 0)
        {
            var item = q.Dequeue();
            result.Add(item);

            if (item?.Children?.Count() > 0)
                foreach (var child in item.Children)
                    q.Enqueue(child);
        }

        return result;
    }
Improve this answer

1 Comment

With .Count() (enumerable) as opposed to .Count (list), you still have to go through the list each time. If you can't avoid that, you might get better performance from .Any() stackoverflow.com/questions/5741617/listt-any-or-count
1

While there are extension methods that enable recursion in LINQ (and probably look like your function), none are provided out of the box.

Examples of these extension methods can be found here or here.

I'd say your function is fine.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.