I don't think RX is the right tool for the job here.
Also, you should use a HashSet to keep track of the visited nodes.
List.Contains() iterates over all elements, so you will introduce O(n^2) behavior.
To flatten the result it's easiest to use Enumerable.SelectMany()
Instead of relying on a extra class to implement GetChildren() you can simply use a delegate Func<T, IEnumerable<T>> getChildren
that specifies how to get the children of the node type in question.
This is how I would do it:
public static IEnumerable<T> DepthFirst<T>(T node,
Func<T, IEnumerable<T>> getChildren,
HashSet<T> visitedNodes)
{
return getChildren(node)
.Where(visitedNodes.Add)
.SelectMany(child => DepthFirst(child, getChildren, visitedNodes))
.Concat(new[] { node });
}
public static IEnumerable<T> DepthFirst<T>(T root,
Func<T, IEnumerable<T>> getChildren)
{
return DepthFirst(root, getChildren, new HashSet<T> {root});
}