Обойти дерево в глубину

Как правильно написали в комментариях, вам нужно декартово произведение множеств (или вы неправильно описали задачу и привели неправильный пример для фиксированного числа множеств).

Для заранее неизвестного числа множеств можно написать такой рекурсивный вариант:

static class Extensions
{
    public static IEnumerable<T> Cartesian<T>(this IEnumerable<IEnumerable<T>> source, Func<T, T, T> aggregator)
    {
        var list = source as List<IEnumerable<T>> ?? source.ToList();
        return CartesianImpl(list, list.Count - 1, aggregator);
    }
    static IEnumerable<T> CartesianImpl<T>(List<IEnumerable<T>> list, int startIndex, Func<T, T, T> aggregator)
    {
        if (startIndex > 0)
        {
            foreach (var y in list[startIndex])
                foreach (var x in CartesianImpl(list, startIndex - 1, aggregator))
                    yield return aggregator(x, y);
        }
        else
        {
            foreach (var e in list[startIndex])
                yield return e;
        }
    }
}

Более простой вариант, с использованием итератора, но возвращающий последовательности немного в другом порядке:

static class Extensions
{
    public static IEnumerable<T> Cartesian<T>(this IEnumerable<IEnumerable<T>> source, Func<T, T, T> aggregator)
    {
        var enumerator = source.GetEnumerator();
        if (!enumerator.MoveNext()) return Enumerable.Empty<T>();
        var result = enumerator.Current;
        while (enumerator.MoveNext())
        {
            var current = enumerator.Current;
            result = result.SelectMany(e => current, (x, y) => aggregator(x, y));
        }
        return result;
    }
}

Используем:

var replies1 = new List<int>() { 1, 4, 7 };
var replies2 = new List<int>() { 2, 5, 8 };
var replies3 = new List<int>() { 3, 6, 9 };
var mas = new List<List<int>>() { replies1, replies2, replies3 };
var res = mas.Cartesian((x, y) => 10 * x + y);
Console.WriteLine(string.Join("\n", res));