Figure 1: State machine-based tree iterators

int TreeIterator::operator++()
{
  // assume that TreeIterator has
  // a member variable: 
  // "string stateSequence;"
     
  if(stack.isEmpty())
     return FINISHED;
     
  while(!stack.isEmpty()) {
    TreeIteratorNode *node = 
        stack.top();

    int   state = node->state();

    // move to the next state    
    node->setState(state+1);  
     
    switch(stateSequence[state]) {
      case '1' :  // Go Left
        if(node->left()) // push the
                         // node
                         // onto the
                         // stack if
                         // available
                         // initial 
                         // state 
                         // index
           stack.push(
             TreeIteratorNode(
               node->left(), 0));
        break;
      case '2' : // Visit the node
        return 1;
      case '3' : // Go Right
        if(node->right())  // push the
                           // node 
                           // onto the
                           // stack if
                           // available
                           // initial 
                           // index
          stack.push(
            TreeIteratorNode(
              node->right(), 0));
        break;
      case '4' : // Finished with this 
                 // sub tree
        stack.pop();
        break;
    }
  }
  // Error if stack is empty!
  //  This means the 
  // sequence was invalid.
     
  return ERROR;
}
//End of File