Extension method to enumerate a hierarchical object

Question

I have a domain object that I have no control over which itself contains a collection of this same type. This is a classical hierarichal representation like in a tree node hierarchy. I would like to be able to enumerate the whole hierarchy in a single call so I came up with this extension method:

public static class MyObjectExtensions
{
    public static IEnumerable<MyObject> FindAllObjectsRecursive(this MyObject myObject)
    {
        var objects = new List<MyObject>();

        objects.Add(myObject);

        foreach (MyObject innerObject in myObject.Objects)
        {
            objects.AddRange(innerObject.FindAllObjectsRecursive());
        }

        return objects;
    }
}

Unfortunately I am not really satisfied by this method because it would definitely cause issues in a large tree span scenario. So I was wondering if anyone would have a solution for that. I did think of using a parameter for the list but I was thinking there must be a better solution.

Here is how I intend to use this method:

var myObject = new MyObject();
var allObjects = myObject.FindAllObjectsRecursive();

And here is the domain object:

public class MyObject
{
    public IEnumerable<MyObject> Objects { get; set; }
}

Answer 1

If you afraid that your tree can be too deep, as mentioned already, you can use Stack or Queue, depending on how you would like to traverse the tree. Here the sample code how to accomplish your task with Queue:

using System.Collections.Generic;
using System.Linq;

public static IEnumerable<MyObject> FindAllObjectsRecursive(this MyObject obj)
{
    var queue = new Queue<MyObject>();
    queue.Enqueue(obj); // Note that you can add first object in the queue constructor

    var result = new List<MyObject>();

    while (queue.Any())
    {
        var current = queue.Dequeue();
        result.Add(current);
        if (null != current.Objects)
        {
            foreach (MyObject inner in current.Objects)
            {
                queue.Enqueue(inner);
            }
        }            
    }

    return result;
}

Answer 2

There is a way, and it is beautiful. Instead of using recursion, you use iteration by placing the top level object on a Stack (or Queue depending on whether you want a depth-first or a breadth-first search). Then you go into a loop where you pop off the first item, check to see if it has descendants, and add them to the stack. By the time the stack/queue is empty you'll have traversed the entire tree.

You were halfway there with your decision to manage a collection that represents the entire set of objects, but the nature of the Stack/Queue allows you to access deeper and deeper properties without having to go deeper and deeper in the call stack.

Example from MSDN on how to traverse a directory tree: http://msdn.microsoft.com/en-us/library/bb513869.aspx

Whether you choose to implement this as an extension method or not is up to you. I also strongly advise asking yourself whether you really need a collection of all descendants, or if you simply want to iterate through all descendants of a certain object? The answer to that question will determine whether the traversal belongs in what would be acting on the top-level object or whether the traversal should be abstracted away.

Answer 3

Option 1 - don't create children lists

One improvement is to avoid creating multiple lists that feed into each-other.
We can do this by passing the list as an argument.

public static ICollection<MyObject> GetDescendents(this MyObject item)
{
    // This could be a List<T>, a Queue<T>, a Stack<T>, etc. Take your pick.
    var allObjects = new List<MyObject>();
    item.GetDescendentsInto(allObjects);
    return allObjects;
}
private static void GetDescendentsInto(this MyObject myObject, ICollection<MyObject> listToPopulate)
{
    listToPopulate.Add(myObject);

    foreach (MyObject innerObject in myObject.Objects)
    {
        innerObject.GetDescendentsInto(listToPopulate);
    }
}

Option 2 - use enumerators and yield

Depending on your concrete situation, you could also use yield to only enumerate the results as you need them.

public static IEnumerable<MyObject> GetDescendentsLazily(this MyObject item)
{
    yield return item;

    foreach (MyObject child in item.Objects)
    {
        var descendents = child.GetDescendents();
        foreach (var descendent in descendents)
        {
            yield return descendent;
        }
    }
}

This has advantages and drawbacks. It gives you support for infinite lists, but it also creates a lot of enumerators.

If you're interested in this, you could avoid recursion by unrolling the list. It will give you a result similar to what @moarboilerplate proposes, but using yield.