#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

class node
{ protected:
    string data;
    vector <node *> child;

  public:
    node(string d)
    { data = d; }

    node * add(node * p)
    { child.push_back(p);
      return this; }

    string getdata()
    { return data; }

    int getnumchildren()
    { return child.size(); }

    node * get(int i)
    { return child[i]; } };

node * mn(string s)
{ return new node(s); }



class stack_frame
{ public:
    string type;
    int where;

    stack_frame(string t)
    { type = t;
      where = 0; }
      
    virtual void print() = 0; };



class reverse_stack_frame: public stack_frame
{ public:
    string s;

    reverse_stack_frame(string s0): stack_frame("R")
    { s = s0; }
    
    virtual void print()
    { cout << "where = " << where << 
              ", s = \"" << s << "\""; } };



class print_stack_frame: public stack_frame
{ public:
    node * p;
    int depth, num, i;

    print_stack_frame(node * p0, int depth0): stack_frame("P")
    { p = p0;
      depth = depth0; }

    virtual void print()
    { cout << "where = " << where <<
              ", p contains \"" << (p == NULL ? "(nothing)" : p->getdata()) << "\""; } };


/* the original recursive versions to show the positions

   type R stack frames
   
      string reverse(const string & s)
      { [position 0]
        if (s.length() <= 1)
          return s;
        return 
           reverse(s.substr(1))
           [position 1]
           + s[0]; }

   type P stack frames
   
      void print(node * p, int depth = 0)
      { [position 0]
        cout << setw(depth*5) << "" << 
                reverse(p->getdata())
                [position 1]
                << "\n";
        int num = p->getnumchildren();
        int i = 0;
        [position 3]
        while (i < num)
        { print(p->get(i), depth+1);
          [position 2]
          i += 1; } }
*/


void print(node * t)
{ string string_return;
  vector <stack_frame *> stack;
  stack.push_back(new print_stack_frame(t, 0));

  while (stack.size() > 0)
  { stack_frame * sf = stack.back();
    if (sf->type == "R")
    { reverse_stack_frame * rsf = (reverse_stack_frame *) sf;

      if (rsf->where == 0)
      { if (rsf->s.length() <= 1)
        { string_return = rsf->s;
          stack.pop_back();
          continue; }
        else
        { stack.push_back(new reverse_stack_frame(rsf->s.substr(1)));
          rsf->where = 1;
          continue; } }

      else if (rsf->where == 1)
      { string_return = string_return + rsf->s[0];
        stack.pop_back();
        continue; } }

    else if (sf->type == "P")
    { print_stack_frame * psf = (print_stack_frame *) sf;

      if (psf->where == 0)
      { cout << setw(psf->depth * 5) << "";
        stack.push_back(new reverse_stack_frame(psf->p->getdata()));
        psf->where = 1;
        continue; }

      else if (psf->where == 1)
      { cout << string_return << "\n";
        psf->num = psf->p->getnumchildren();
        psf->i = 0;
        psf->where = 3;
        continue; }

      else if (psf->where == 2)
      { psf->i += 1;
        psf->where = 3;
        continue; }

      else if (psf->where == 3)
      { if (psf->i < psf->num)
        { stack.push_back(new print_stack_frame(psf->p->get(psf->i), psf->depth + 1));
          psf->where = 2;
          continue; }
        else
        { stack.pop_back();
          continue; } } } } }
      

int main()
{ node * t = mn("ant")
                      ->add(mn("bat")
                                     ->add(mn("egg")
                                                    ->add(mn("kit"))
                                                    ->add(mn("log")))
                                     ->add(mn("fig"))
                                     ->add(mn("git")
                                                    ->add(mn("map"))
                                                    ->add(mn("nut"))
                                                    ->add(mn("old"))
                                                    ->add(mn("pig"))))
                      ->add(mn("cat")
                                     ->add(mn("hat")))
                      ->add(mn("dog")
                                     ->add(mn("ink")
                                                    ->add(mn("qat"))
                                                    ->add(mn("rat")))
                                     ->add(mn("jug")
                                                    ->add(mn("sud"))
                                                    ->add(mn("tip"))));
  print(t); }