Binary search tree IEnumerator.MoveNext() non recursive in order traversal implementation. How to?

Question

After having built a binary search tree BST<Tkey,TValue> which consists of BSTNode<Tkey,TValue> nodes I am trying to implement the IEnumerable interface for it.

This is the how I construct the BSTNodeEnumrator<Tkey,TValue>:

public class BSTNodeEnumerator<TKey, TValue> : IEnumerator<BSTNode<TKey, TValue>> where TKey : IComparable<TKey>
{
    private Stack<BSTNode<TKey, TValue>> _stack;

    public BSTNodeEnumerator(BSTNode<TKey, TValue> root)
    {
        _stack = new Stack<BSTNode<TKey, TValue>>();
        _current = null;
        _root = root;
    }

    // ... rest of the implementation
}

I pass in root node and _current is the result of the enumeration. I am also trying to use a stack for this as I do not keep track of the parent node as in AVL BST.

Now I want the enumerator to traverse the tree in order + in a non recursive manner. That should result in a sorted enumeration as well due to the properties of a bst, which is great as that's exactly what I want to achieve.

The non-recursive algorithm for in order traversal in pseudo-code as in this wikipedia article

    iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

We can transform the algorithm into this c# code:

public BSTNode<Tkey,TValue> Next() 
{
   while (_stack.Count > 0 || _current != null) 
    {
         if (_current != null)
         {
          _stack.Push(_current);
          _current = _current.left;
         }
         else
         {
          _current = _stack.Pop();
          BSTNode<Tkey,TValue> result = _current;
          _current = _current.Right;
         }
    }
    return result;
}

But that is not the required bool MoveNext() implementation as I have to return a bool. True if I did set _current to an appropriate node, false if I am at the end.

How should I go about implementing public bool MoveNext() ? The main thing that I can't wrap my head around is that If I want to transform BSTNode<Tkey,TValue> Next() into bool MoveNext() I have to return true instead of simply visiting the node BSTNode<Tkey,TValue> result = _current; and only after that set _current = _current.Right; which I obviously can't do.

Answer 1

The caller is looping over the enumeration (probably in a foreach-loop). Therefore you can abort your loop each time you want to return a result. A problem arises, because _current = _current.Right; must be executed after the result has been determined. Therefore I am introducing a new variable _result.

private BSTNode<TKey, TValue> _result;

bool IEnumerator.MoveNext()
{
    while (_stack.Count > 0 || _current != null)
    {
        if (_current != null)
        {
            _stack.Push(_current);
            _current = _current.left;
        }
        else
        {
            _current = _stack.Pop();
            _result = _current;
            _current = _current.Right;
            return true;
        }
    }
    return false;
}

BSTNode<TKey, TValue> IEnumerator<BSTNode<TKey, TValue>>.Current
{
    get { return _result; }
}

Note that looping over an enumeration consists of first calling MoveNext() and testing the Boolean result. Then using the value returned by Current if true was returned.