title: In-order traversal complexity in a binary search tree (using iterators)?
body: <p>Related question: <a href="https://stackoverflow.com/questions/9658700/time-complexity-of-inorder-tree-traversal-of-binary-tree-on">Time Complexity of InOrder Tree Traversal of Binary Tree O(N)?</a>, however it is based on a traversal via recursion (so in O(log N) space) while iterators allow a consumption of only O(1) space.</p>
  
  <p>In C++, there normally is a requirement that incrementing an iterator of a standard container be a O(1) operation. With most containers it's trivially proved, however with <code>map</code> and such, it seems a little more difficult.</p>
  
  <ul>
  <li>If a <code>map</code> were implemented as a skip-list, then the result would be obvious</li>
  <li>However they are often implemented as red-black trees (or at least as binary search trees)</li>
  </ul>
  
  <p>So, during an in-order traversal there are moments where the "next" value is not so easily reached. For example should you be pointing at the bottom-right leaf of the left subtree, then the next node to traverse is the root, which is <code>depth</code> steps away.</p>
  
  <p>I have tried "proving" that the algorithmic complexity (in terms of "steps") was <em>amortized</em> O(1), which seems alright. However I don't have the demonstration down yet.</p>
  
  <p>Here is a small diagram I traced for a tree with a depth of 4, the numbers (in the place of the nodes) represent the number of steps to go from that node to the next one during an in-order traversal:</p>
  
  <pre><code>       3
     2       2
   1   1   1   1
  1 2 1 3 1 2 1 4
  </code></pre>
  
  <p><em>Note: the right-most leaf has a cost of 4 in case this would be a sub-tree of a larger tree.</em></p>
  
  <p>The sum is 28, for a total number of nodes of 15: thus a cost less than 2 per node, in average, which (if it holds up) would be a nice amortized cost. So:</p>
  
  <ul>
  <li>During in-order traversal, is incrementing the iterator really O(1) for a balanced (and full) binary search tree ?</li>
  <li>May the result be extended to cover non-full binary search trees ?</li>
  </ul>