Flatten a tree to a collection of nodes I have implemented simple tree class as follows:
public class MoveTreeNode
{
    public MoveTreeNode Parent
    {
        get;
        set;
    }

    private List&lt;MoveTreeNode&gt; children = new List&lt;MoveTreeNode&gt;();

    public IEnumerable&lt;MoveTreeNode&gt; Children
    {
        get
        {
            return children;
        }
    }

    public void Add(MoveTreeNode child)
    {
        child.Parent = this;
        children.Add(child);
    }

    private IEnumerable&lt;MoveTreeNode&gt; Flatten()
    {
        yield return this;

        foreach(var child in Children.Select(x=&gt; x.Flatten()).SelectMany(x=&gt;x))
        {
            yield return child;
        }
    }
}

This works, but I have concerns about the following line:
foreach(var child in Children.Select(x=&gt; x.Flatten()).SelectMany(x=&gt;x))
Since I'm using yield I'd prefer to gain some of the benefits of lazy evaluation but I fear that while each child of the root will be lazily evaluated, the childrens' children, etc will be evaluated at once when their parents are evaluated.
Is there some way I can refactor this to make the most of lazy evaluation, or am I better off leaving it this way?
I think you want to flatten each child in turn:

private IEnumerable&lt;MoveTreeNode&gt; Flatten()
{
    yield return this;

    foreach (var node in Children.SelectMany(child =&gt; child.Flatten()))
    {
        yield return node;
    }
}


That way you won't flatten the whole tree first.

Edit:

It's more difficult to talk about things so let's look at some code. SelectMany is roughly equal to:

public static IEnumerable&lt;TOut&gt; SelectMany&lt;T, TOut&gt;(this IEnumerable&lt;T&gt; source, Func&lt;T, IEnumerable&lt;TOut&gt;&gt; selector)
{
    foreach (var item in source)
    {
        foreach (var subItem in selector(item))
        {
            yield return subItem;
        }
    } 
}


So as you can see, we will definitely get all of the nodes and if you stop iterating before the end (e.g. by calling .First()) you will only call Flatten() on a single child.