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

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 getdata()
    { return data; }

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

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

node * mn(string s)   // mn calls constructor, but it shorter to type
{ return new node(s); }

struct AR
{ node * p;
  int depth;
  int num;
  int i;
  int pos;
  AR(node * newnode, int newdepth)
  { p = newnode;
    depth = newdepth;
    pos = 0; } };

void print(node * p, int depth = 0)
{ // position 0
  cout << setw(depth*5) << " " << p->getdata() << "\n";
  int num = p->getnumchildren();
  int i = 0;
  while (i < num)
  { print(p->get(i), depth+1);
    // position 1
    i += 1; } 
}

void nr_print(node * root)
{ deque<AR *> queue;
  queue.push_back(new AR(root, 0));
  while (! queue.empty())
  { AR * curr = queue.front();
    if (curr->pos == 0)
    { cout << setw(curr->depth*5) << " " << curr->p->getdata() << "\n";
      curr->num = curr->p->getnumchildren();
      curr->i = 0;
      if (curr->i < curr->num)
      { queue.push_back(new AR(curr->p->get(curr->i), curr->depth + 1));
        curr->pos = 1;
        continue; }
      queue.pop_front();
      continue; }
    else // if (curr->pos == 1)
    { curr->i += 1;
      if (curr->i < curr->num)
      { queue.push_back(new AR(curr->p->get(curr->i), curr->depth + 1));
        curr->pos = 1;
        continue; }
      queue.pop_front();
      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); }