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

  node * setL(node * p)
  { left = p;
    return this; }

  node * setR(node * p)
  { right = p;
    return this; }
};

node * n(string s)
{ return new node(s); }

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

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***"; }

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 * e;

  e = n("emu")->setL(n("cat")->setL(n("ant")
                                            ->setR(n("bat")))
                             ->setR(n("dog")))
              ->setR(n("ink")->setL(n("gar")->setL(n("fly"))
                                            ->setR(n("hat")))
                             ->setR(n("jar")));

  print1(e);
  print2(e);

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