Traversing a C# Binary Search Tree Iteratively and with Yield-Return

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)
      n = n.left;
      n = s.Pop();
      yield return;
      n = n.right;

This method could be called like so:

BinarySearchTree bst = new BinarySearchTree();
etc., etc.

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)

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.

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