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

using namespace std;

struct node
{ string data;
  node * left, * right;

  node(string d)
  { data = d;
    left = NULL;
    right = NULL; } };

class AR
{ public:
    node * t;
    int depth;
    int where;
        
    AR(node * init_t, int init_depth, int init_where = 1)
    { t = init_t;
      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; } };

class tree
{ protected:
    node * root;

  public:
    tree()
    { root = NULL; }

    void add(node * & t, string s)
    { if (t == NULL)
        t = new node(s);
      else if (s < t->data)
        add(t->left, s);
      else
        add(t->right, s); }

    void add(string s)
    { add(root, s); }

//
//  the unwanted recursive print:
//
//  void print(node * t, int depth)
//  { /* this is position 1 */
//    if (t == NULL)
//      return;
//    print(t->right, depth + 1);   // right first because the picture is rotated
//    /* this is position 2 */
//    cout << setw(depth * 5) << "" << t->data << "\n";
//    print(t->left, depth + 1);
//    /* this is position 3 */ }
//
//  void print()
//  { print(root, 0); }
//

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

        if (top.where == 1)
        { if (top.t == NULL)
          { S.pop();
            continue; }
          S.push(new AR(top.t->left, top.depth + 1));
          top.where = 2;
          continue; }

        else if (top.where == 2)
        { cout << setw(top.depth * 5) << "" << top.t->data << "\n";
          S.push(new AR(top.t->right, top.depth + 1));
          top.where = 3;
          continue; }

        else if (top.where == 3)
        { S.pop();
          continue; } } } };

int main()
{ tree t;
  t.add("egg"); t.add("pig"); t.add("dog"); t.add("nut"); t.add("ant");
  t.add("jug"); t.add("qat"); t.add("rat"); t.add("bat"); t.add("git");
  t.add("map"); t.add("kit"); t.add("ink"); t.add("sud"); t.add("log");
  t.add("hat"); t.add("cat"); t.add("old"); t.add("fig"); t.add("tip");
  t.nr_print(); }