Recursively Traversing IEnumerable<T>

Most of the samples I saw about traversing an IEnumerable<T> use recursion, this can cause some overload in the stack depending on the hierarchy depth. The version I propose use a Queue<T> to achieve the same; note that this is I a common algorithm named Breadth-first search, and note that you can use a Stack<T> instead to turn to Depth-first search algorithm. Here you have the extension method:

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> items,
    Func<T, IEnumerable<T>> itemsEnumerator)
{
    var queue = new Queue<T>(items);
    while (queue.Count > 0)
    {
        var item = queue.Dequeue();
        yield return item;

        foreach (var child in itemsEnumerator(item))
        {
            queue.Enqueue(child);
        }
    }
}

The use of this extension method is really simple, for example, if we have the following class:

public class Node
{
    public Node()
    {
        this.Nodes = new List<Node>();
    }
          
    public string Name { get; set; }
           
    public List<Node> Nodes { get; private set; }
}

We can use the extension method above to traverse the hierarchy in the following way:

node.Nodes.Traverse(n => n.Nodes);
Published Monday, March 21, 2011 10:13 AM by marianor
Filed under:

Comments

No Comments