title: Implementing an iterator over a binary search tree
body: <p>I've been coding up a bunch of different binary search tree implementations recently (AVL, splay, treap) and am curious if there's a particularly "good" way to write an iterator to traverse these structures.  The solution I've used right now is to have each node in the BST store pointers to the next and previous elements in the tree, which reduces iteration to a standard linked-list iteration.  However, I'm not really satisfied with this answer.  It increases the space usage of each node by two pointers (next and previous), and in some sense it's just cheating.</p>
  
  <p>I know of a way of building a binary search tree iterator that uses O(h) auxiliary storage space (where h is the height of the tree) by using a stack to keep track of the frontier nodes to explore later on, but I've resisted coding this up because of the memory usage.  I was hoping there is some way to build an iterator that uses only constant space.</p>
  
  <p>My question is this - is there a way to design an iterator over a binary search tree with the following properties?</p>
  
  <ol>
  <li>Elements are visited in ascending order (i.e. an inorder traversal)</li>
  <li><code>next()</code> and <code>hasNext()</code> queries run in O(1) time.</li>
  <li>Memory usage is O(1)</li>
  </ol>
  
  <p>To make it easier, it's fine if you assume that the tree structure isn't changing shape during the iteration (i.e. no insertions, deletions, or rotations), but it would be really cool if there was a solution that could indeed handle this.</p>