In recent blog posts I’ve described a C# implementation of a binary search tree where each data is a (long) integer. In one of these posts I presented code to copy the contents of an instance of a binary search tree into an array, using recursion and the C# yield-return mechanism. I try to avoid using recursion as much as possible (except in situations where it leads to much cleaner calls) so I refactored the recursive data-copy code to an iterative approach:

public IEnumerable<long> FetchValues()
{
  Stack<TreeNode> s = new Stack<TreeNode>();
  TreeNode n = this.root;
  while (s.Count > 0 || n != null)
  {
    if (n != null)
    {
      s.Push(n);
      n = n.left;
    }
    else
    {
      n = s.Pop();
      yield return n.data;
      n = n.right;
    }
  }
}

This method could be called like so:

BinarySearchTree bst = new BinarySearchTree();
bst.Insert(50);
etc., etc.
bst.Insert(67);

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

for (int j = 0; j < array.Length; ++j)
  Console.WriteLine(array[j]);

The FetchValues member method uses a stack to perform an inorder traversal of the tree. The while condition is a bit tricky, and in fact so is the logic. In my opinion, this scenario is a tie when it comes to the choice between using recursion, as in my earlier post, or using an iterative approach shown here.