#include <iostream>
#include <string>

struct node
{ string data;
  node * left, * right;
  node (string d="", node * l=NULL, node * r=NULL)
  { data=d;
    left=l;
    right=r; } };

node * tree(string d, node * l, node * r)
{ return new node(d, l, r); }

node * example = tree("horse", tree("cat", tree("ant", NULL,
                                                       tree("bat", NULL, NULL)),
                                           tree("emu", tree("cow", NULL,
                                                                   tree("dog", NULL, NULL)),
                                                       tree("goat", tree("frog", NULL, NULL),
                                                                    tree("hat", NULL, NULL)))),
                               tree("penguin", tree("llama", tree("jeff", tree("ibis", NULL, NULL),
                                                                          tree("koala", NULL, NULL)),
                                                             tree("mouse", NULL, NULL)),
                                               tree("tiger", tree("stoat", NULL, NULL),
                                                             NULL)));

void print(node * n)
{ cout << "(";
  if (n!=NULL)
  { print(n->left);
    cout << n->data;
    print(n->right); }
  cout << ")"; }

void __main()
{ print(example);
  cout << "\n"; }

/* print naturally has three sections:

   void print(node * n)
   { // POINT A IS HERE
     cout << "(";
     if (n!=NULL)
     { print(n->left);
       // POINT B IS HERE
       cout << n->data;
       print(n->right); }
     // POINT C IS HERE
     cout << ")";
     // POINT D IS HERE
   }

   Point A is significant because every call to print starts there

   Point B is significant because it is almost another starting
   point. The first recursive call is like a jump back to A, but
   eventually when all the recursions are done, control will jump 
   back to B

   Point C is significant for exactly the same reason. The second
   recursive call is another jump back to A, but when it is all
   done, control will jump back to C.

   There are four places where the flow of control jumps. From
   main() and the two recursive calls, there is always a jump to
   point A. It is only at the end of the function, point D, that
   a call is over, and control may jump back to point B, point C,
   or main.

   It could be thought of like this:

         A: cout << "("
            if (n!=NULL)
            { remember what n is now,
              remember to eventually come back to B
              n=n->left
              goto A }
            else
              goto C

         B: cout << n->data
            remember what n is now,
            remember to eventually come back to C
            n=n->right
            goto A

         C: cout << ")"
            go back to the last value of n you were remembering
            goto the last label you were remembering.

Or it could be written less offensively like this
                                                       */
                                            struct stack
                                            { int num;
                                              string wheres[100];
                                              node * ptrs[100];
                                              stack()
                                              { num=0; }
                                              bool empty()
                                              { return num==0; }
                                              void push(string s, node * n)
                                              { wheres[num]=s;
                                                ptrs[num]=n;
                                                num+=1; }
                                              void pop(string & s, node * & n)
                                              { num-=1;
                                                n=ptrs[num];
                                                s=wheres[num]; } };
void nr_print(node * n)
{ stack s;
  string where="A";
  while (true)
  {
    if (where=="A")
    {
      cout << "(";
      if (n!=NULL)
      { s.push("B", n);
        n=n->left;
        where="A"; }
      else
        where="C";
    }
    if (where=="B")
    {
      cout << n->data;
      s.push("C", n);
      n=n->right;
      where="A";
    }
    if (where=="C")
    { cout << ")";
      if (s.empty())
        break;
      s.pop(where, n); 
    }
  }
}

void _main()
{ nr_print(example);
  cout << "\n"; }

/* Now that there is no recursion, the whole thing can be encapsulated
   in an object which provides the strings one at a time as needed, not
   all at once.  An enumerator for trees. */

struct Enumeratree
{ stack s;
  node * n;
  string where;
  string current;
  bool alive;

  Enumeratree(node * n0)
  { n=n0;
    where="A";
    alive=true;
    progress(); }

  void progress()
  { while (true)
    {
      if (where=="A")
      {
        if (n!=NULL)
        { s.push("B", n);
          n=n->left;
          where="A"; }
        else
          where="C";
      }
      if (where=="B")
      {
        current = n->data;
        s.push("C", n);
        n=n->right;
        where="A";
        return;
      }
      if (where=="C")
      { if (s.empty())
        { alive=false;
          return; }
        s.pop(where, n); 
      } } }

  bool more()
  { return alive; }

  string next()
  { string answer=current;
    progress();
    return answer; } };

void main()
{ Enumeratree en(example);
  for (int i=1; en.more(); i+=1)
    cout << i << ": " << en.next() << "\n"; }