Traversing a C# Binary Search Tree using Recursion and Yield-Return

In a recent blog post I presented code for a simple but effective binary search tree, where the data is a (long) integer, implemented using the C# language. Today I wanted to traverse the binary search tree to transfer the contents of the tree into an array. I wondered if I could use the yield-return mechanism and it turns out it is possible:

public IEnumerable<long> FetchValues() // public interface
  foreach (long v in FetchValues(this.root))
    yield return v;

private IEnumerable<long> FetchValues(TreeNode rootNode) // worker
  if (rootNode != null)
    foreach (long v in FetchValues(rootNode.left)) yield return v;
    yield return;
    foreach (long v in FetchValues(rootNode.right)) yield return v;

Calling this code might look something like:

BinarySearchTree bst = new BinarySearchTree();

long[] array = new long[bst.Count];
int i = 0;
foreach (long v in bst.FetchValues())
  array[i++] = v;

The FetchValues method is a bit exotic because it uses both recursion and the C# yield-return mechanism. As is often the case for recursive methods, there is a private worker method which accepts the current root node as a parameter (so that it can be used to pass left and right sub-trees recursively), and there is a public interface which calls the private worker. The private worker uses an in-order traversal to extract and emit one value at a time from the tree via yield-return. The public method consumes one value at a time from the private worker using foreach and emits the values using yield-return. All the buffering plumbing code is done behind the scenes by the C# compiler. This technique is exotic but seems to be a reasonably practical solution to the problem of transferring the contents of a C# binary search tree to an array. I’ve also coded a version of this functionality which does not use recursion — I’ll post that variation when I get a chance.

This entry was posted in Software Test Automation. Bookmark the permalink.