#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)
{ if (p == NULL)
    p = new node(v, NULL, NULL);
  else if (v < p->data)
    ins(p->left, v);
  else if (v > p->data)
    ins(p->right, v); }

// this is the C language's way of making references
void ins_C(node * * p, int v)
{ if (* p == NULL)
    * p = new node(v, NULL, NULL);
  else if (v < (* p)->data)
    ins(& (* p)->left, v);
  else if (v > (* p)->data)
    ins(& (* p)->right, v); }

/* example call for the above

   node * tree = NULL;
   ins_C(....

   ins_C(& tree, 8);
*/


void ins_with_loop_1_worker(node * p, int v)
{ node * prev = NULL;
  while (p != NULL)
  { prev = p;
    if (v == p->data)
      return;
    else if (v < p->data)
      p = p->left;
    else
      p = p->right; }
  if (v < prev->data)
    prev->left = new node(v);
  else
    prev->right = new node(v); }

void ins_with_loop_1(node * & p, int v)
{ if (p == NULL)
    p = new node(v);
  else
    ins_with_loop_1_worker(p, v); }

void ins_with_loop_2_worker(node * p, int v)
{ while (p != NULL)
  { if (v == p->data)
      return;
    else if (v < p->data)
    { if (p->left == NULL)
      { p->left = new node(v);
        return; }
      p = p->left; }
    else
    { if (p->right == NULL)
      { p->right = new node(v);
        return; }
      p = p->right; } } }

node * insert(node * p, int v)
{ if (p == NULL)
    return new node(v);
  if (v == p->data)
    return p;
  if (v < p->data)
    p->left = insert(p->left, v);
  else
    p->right = insert(p->right, v);
  return p; }

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

bool find(node * p, int wanted)
{ if (p == NULL)
    return false;
  if (wanted == p->data)
    return true;
  if (wanted < p->data)
    return find(p->left, wanted);
  else
    return find(p->right, wanted); }

bool find_with_loop(node * p, int wanted)
{ while (p != NULL)
  { if (wanted == p->data)
      return true;
    if (wanted < p->data)
      p = p->left;
    else
      p = p->right; }
  return false; }

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