#include <iostream>
#include <string>

using namespace std;

class Tree;

class TreeNode {
private:
    TreeNode  *left;
    TreeNode  *right;
    string    word;
public:
              TreeNode(string);
    void      SetWord(string);
    void      SetRight(TreeNode*);
    void      SetLeft(TreeNode*);
    string    GetWord();
    TreeNode* GetLeft();
    TreeNode* GetRight();
    
};

TreeNode::TreeNode(string w="")
{
    word=w;
    left=right=0;
}

void TreeNode::SetWord(string w)
{word=w;}

void TreeNode::SetRight(TreeNode* j)
{right=j;}

void TreeNode::SetLeft(TreeNode* j)
{left=j;}

string TreeNode::GetWord()
{return word;}

TreeNode* TreeNode::GetLeft()
{return left;}

TreeNode* TreeNode::GetRight()
{return right;}


class Tree {
public:
    Tree() ;
    void Readlist();
    void Insert(string);
    void Insert(TreeNode*, string);
    bool Member(string);
    bool Member(TreeNode*, string);
private:
    TreeNode *root;
};

Tree::Tree(){
    root = 0;
}

void Tree::Readlist(){
  int numtimes;
  string x;
  cout << endl;
  cout << "num of times" << endl;
  cin >> numtimes;
  for ( int i = 1 ; i <= numtimes ; i = i + 1 )
   { cout << "Input String" << endl;
     cin >> x;
     cout << x << endl;
     Insert( x );
   }
}

void Tree::Insert(string x) {
  TreeNode *current = root;
  if (current==0)
     { root = new TreeNode(x);
       return;
     }
  Insert(root,x); 
}

void Tree::Insert(TreeNode *ptr, string x)
{ TreeNode *current;
  cout<< "word in Insertit " << ptr->GetWord() << endl;
  if (x < ptr->GetWord())
     {if (ptr->GetLeft() == 0)
         {current = new TreeNode(x);
          ptr->SetLeft(current);
         }
      else Insert(ptr->GetLeft(),x);
     }
  else if (x == ptr->GetWord())
       {return;}
  else 
     {if (ptr->GetRight() == 0)
         {current = new TreeNode(x);
          ptr->SetRight(current);
         }
      else Insert(ptr->GetRight(),x);
     }
}

bool Tree::Member(string x) {
  TreeNode *current = root;
  if (root==0) return false;
  return Member(root,x);
}

bool Tree::Member(TreeNode *ptr,string x)
{ if (ptr->GetWord() == x) return true;
  if (x < ptr->GetWord() && ptr->GetLeft() != 0)
     return Member(ptr->GetLeft(),x);
  else if (x > ptr->GetWord() && ptr->GetRight() != 0)
     return Member(ptr->GetRight(),x);
  return false;
}
     

main()
{ int numtests;
  string newelem;

  Tree t;
  t.Readlist();

  cout << endl;
  cout << "num of tests" << endl;
  cin >> numtests;
  for ( int i = 1 ; i <= numtests ; i = i + 1 )
    { cout << "Input Test String" << endl;
      cin >> newelem;
      cout << newelem << "IS A MEMBER?"
           << t.Member(newelem) << endl;
    }
}