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.