I have recently been brushing up on my Computer Science training, implementing various data structures and algorithms, O(log n) searching, that sort of thing. While traversing a binary tree returning it's contents in sorted order, I really wanted to put the yield keyword to use.

The yield keyword was introduced in .NET 2.0 and is used when added iteration features to a class. Typically this means when implementing the IEnumerable or IEnumerable<T> interfaces.

One of the most striking examples I have seen that demonstrates how it works is a simple method that returns an iterator over the numbers 1 to 10.

public IEnumerator<int> GetEnumerator() {
    yield return 1;
    yield return 2;
    yield return 3;
    yield return 4;
    yield return 5;
    yield return 6;
    yield return 7;
    yield return 8;
    yield return 9;
    yield return 10;
}

I think this simple-as-they-come example really represents what is going on here.

The compiler uses this method to put together an iterator. When the first MoveNext() is called, the method executes until the first yield is reached. The value is returned and the state is saved, when the next MoveNext() is called, the code keeps running from where it was until the next yield is reached.

The iterator reaches its end when the function has no more statements to execute, or a yield break; is called.

I've long liked this concept, but rarely had any use for it that wasn't nearly as trivial as the example above. The big reason is that most of our data structures are already written for us these days. Need a list? Grab it from System.Collections. Therefore I rarely need to iterate in anything but a linear fashion.

So it wasn't until my recent adventures into re-learning some Computer Science theory that I was presented with a good chance to put this to work.

As I was saying, I was using a binary tree to store and sort a set of int's and then needed to pull them back out again in order. For any given node of the tree, this means returning the Left branch followed by the node's own value followed by the Right branch. By implementing the IEnumerable<int> interface on my Node class I was exposing the capability to use foreach(int i in Node) {} to return the values. All I needed was the code for the iterator.

public IEnumerator<int> GetEnumerator() {
    if (Left != null) {
        foreach (int i in Left) {
            yield return i;
        }
    }
    yield return Value;
    if (Right != null) {
        foreach (int i in Right) {
            yield return i;
        }
    }
}

Now I am not going to declare this is a perfect implementation to traverse a Binary Tree. I am not certain exactly what code this compiles down to, but assuming it becomes recursive makes it less than ideal.

Putting that aside for the moment however, I was really impressed with how succinctly this let me express how I wanted the code to behave.

All you could ask for on top of this at a language level is something like a yield iterate Left;

Now that would really cut the code down.