A C# Extension to Recursively Select All Descendents

Introduction

.NET's SelectMany extension methods select only the immediate children of the source. Here, I present two IEnumerable<T> extension methods called SelectManyRecursive and SelectManyAllInclusive. The first will select only the descendents and the second will select the descendents and the items in the source collection. I include also a test program to show how it works.

Using the Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace SelectManyRecursive
{
    public static class Extensions
    {
        public static IEnumerable<T> SelectManyRecursive<T>
                (this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
        {
            var result = source.SelectMany(selector);
            if (!result.Any())
            {
                return result;
            }
            return result.Concat(result.SelectManyRecursive(selector));
        }
 
        public static IEnumerable<T> SelectManyAllInclusive<T>
               (this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
        {
            return source.Concat(source.SelectManyRecursive(selector));
        }
    }
 
    class Test
    {
        int _level;
        public List<Test> Children = new List<Test>();
 
        static Random rand = new Random(DateTime.Now.Millisecond);
        public static int maxLevels = 5;
        public static int total = 0;
 
        public Test() : this(1)
        {
        }
 
        private Test(int level)
        {
            ++total;
            _level = level;
            if (level < maxLevels)
            {
                int numChildren = rand.Next(10) + 1;
                ++level;
                while (numChildren-- > 0)
                {
                    Children.Add(new Test(level));
                }
            }
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            List<Test> root = new List<Test> { new Test(), new Test() };
            var descendents = root.SelectManyRecursive(t => t.Children);
            int descendantsCount = descendents.Count();
 
            var all = root.SelectManyAllInclusive(t => t.Children);
            var count = all.Count();
 
            Console.WriteLine($@"Total Test instances = {Test.total}
Total descendents collected = {descendantsCount}.
 
Note that 'Total descendents' will correctly be {root.Count} less than
'Total Test instances' because SelectManyRecursive selects only the descendents.
 
SelectManyAllInclusive (count = {count}) will select all items including from the source.
 
Press enter to continue:");
            Console.Read();
        }
    }
}

Points of Interest

There's a more efficient non-recursive algorithm than the one presented.

History

• 8 March 2017: First version
• 9 March 2017: changed to use result.Any() instead of .ToList() and .Count because .ToList() can result in unnecessary overhead.