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

using namespace std;

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

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

string find(node * t, string x)
{ while (t != NULL)
  { cout << "t not NULL, looking at " << t->data << "\n";
    if (t->data == x)
      return t->data;
    if (x < t->data)
      t = t->left;
    else
      t = t->right; }
  return "***NOT FOUND***"; }

node * insert(string x, node * t)
{ // returns same tree as it was given, but with one extra node added
  // ignore repeated values
  if (t == NULL)
    return new node(x);
  if (x == t->data)
    return t;
  if (x < t->data)
    t->left = insert(x, t->left);
  else
    t->right = insert(x, t->right);
  return t; }

void insert2(string x, node * & t)
{ if (t == NULL)
  { t = new node(x);
    return; }
  node * ptr = t, * prev = NULL;
  while (ptr != NULL)
  { if (x < ptr->data)
    { prev = ptr;
      ptr = ptr->left; }
    else
    { prev = ptr;
      ptr = ptr->right; } }
  if (x < prev->data)
    prev->left = new node(x);
  else
    prev->right = new node(x); }

void print1(node * t)
{ if (t == NULL)
    return;
  print1(t->left);
  cout << t->data << "\n";
  print1(t->right); }

int depth = 1;

void print2(node * t)
{ if (t == NULL)
    return;
  depth += 1;
  print2(t->left);
  depth -= 1;
  cout << setw(depth*3) << "" << t->data << "\n";
  depth += 1;
  print2(t->right);
  depth -= 1; }

int main()
{ node * root = NULL;

  while (true)
  { cout << "insert: ";
    string s;
    cin >> s;
    if (s == "*") break;
    insert2(s, root);
    print2(root); }

  while (true)
  { cout << "look for: ";
    string s1, s2;
    cin >> s1;
    s2 = find(root, s1);
    cout << "result is " << s2 << "\n"; }
}