#include <iostream>
#include <iomanip>

using namespace std;

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

  node(int v, node * L = NULL, node * R = NULL)
  { data = v;
    left = L;
    right = R; } };

void ins(node * & p, int v)
{ cout << "inserting " << v << " at " << p << ":\n";
  if (p == NULL)
  { p = new node(v, NULL, NULL);
    cout << "  create new node " << p << "\n"; }
  else if (v == p->data)
  { }
  else if (v < p->data)
  { cout << "  moving left\n";
    ins(p->left, v); }
  else
  { cout << "  moving right\n";
    ins(p->right, v); } }

void print(node * p)  // print every int reachable from p, in ascending order
{ if (p == NULL)
    return;
  print(p->left);
  cout << p->data << " at " << p << "\n";
  print(p->right); }

void str_print(node * p, int ind = 0)
{ if (p == NULL)
    return;
  str_print(p->right, ind + 1);
  cout << setw(ind * 3) << "";
  cout << p->data << "\n";
  str_print(p->left, ind + 1); }

int main()
{ node * tree = NULL;
  ins(tree, 56);
  cout << "\n";
  ins(tree, 21);
  cout << "\n";
  ins(tree, 77);
  cout << "\n";
  ins(tree, 1);
  cout << "\n";
  ins(tree, 12);
  cout << "\n";
  ins(tree, 19);
  cout << "\n";
  ins(tree, 95);
  cout << "\n";
  ins(tree, 75);
  cout << "\n";
  ins(tree, 46);
  cout << "\n";
  ins(tree, 69);
  cout << "\n";
  ins(tree, 40);
  cout << "\n";
  print(tree);
  cout << "\n";
  str_print(tree); }