#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; }

      // e.g. in n->add(m); what's returned is n

    string get_data()
    { return data; }

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

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

node * mn(string s)   // mn calls constructor, but it shorter to type
{ return new node(s); }
    
class AR
{ public:
    node * p;
    int depth;
    int num;
    int i;
    int where;
        
    AR(node * init_p, int init_depth, int init_where = 1)
    { p = init_p;
      depth = init_depth;
      where = init_where; } };

class stack: public vector <AR *>
{ public:

    void push(AR * a)
    { push_back(a); }

    AR * pop()
    { AR * result = back();
      pop_back();
      return result; }

    AR * top() const
    { return back(); }

    bool not_empty() const
    { return size() > 0; } };
  
//
// this is the original recursive print, it won't be used any more
//
// void print(node * p, int depth = 0)
// { /* this is position 1 */
//   cout << setw(depth * 5) << " " << p->get_data() << "\n";
//   int num = p->get_num_children();
//   int i = 0;
//   /* this is position 2 */
//   while (i < num)
//   { print(p->get_child(i), depth + 1);
//     /* this is position 3 */
//     i += 1; } }
//

void nr_print(node * root)
{ stack S;
  S.push(new AR(root, 0));
  while (S.not_empty())
  { AR & top = * S.top();

    if (top.where == 1)
    { cout << setw(top.depth * 5) << " " << top.p->get_data() << "\n";
      top.num = top.p->get_num_children();
      top.i = 0;
      top.where = 2;
      continue; }

    else if (top.where == 2)
    { if (top.i < top.num)
      { S.push(new AR(top.p->get_child(top.i), top.depth + 1));
        top.where = 3;
        continue; }
      else
      { S.pop();
        continue; } }

    else if (top.where == 3)
    { top.i += 1;
      top.where = 2;
      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"))));
  nr_print(t); }