#include <iostream>

using namespace std;

/* intBinarySearchTree defines a binary search tree with integer values.
Each node holds a key, and a pointer to left and right subtrees. (A key
in an interior node is not also in a leaf */



class intBinarySearchTree {
private: int Key;
        intBinarySearchTree *Left, *Right;

/* Constructor */
public: intBinarySearchTree(int N): /* Construct leaf */
  Key(N), Left(NULL), Right(NULL) /* Initialization. Key=I etc. Weird 
                                     C++ syntax, only for constructors */
  { }   /* Empty body of constructor */


/* Method find(N) returns true if N is in the tree; else false. 
find(N) is true if either N is the value of the root, or N is in one of
the subtrees */


bool find(int N)
{ if (Key == N) return(true);
  else if (N < Key) 
         if (Left==NULL) return(false); else return Left->find(N);
  else   if (Right==NULL) return(false); else return Right->find(N);
} 

/* Method findAndReport(N) prints out the result of searching for N */

void findAndReport(int N)
{ if (find(N)) cout << N << " in tree.\n";
  else cout << N << " not in tree.\n";
}

/* Method insert(N) adds N to the tree.  If N is already in the tree, do 
nothing.  If it can be placed as a child of the current node, place it.
Otherwise, recursively insert it in the proper subtree. */

void insert(int N)
{ if (Key == N) return;
  else if (N < Key) 
         if (Left==NULL) Left = new intBinarySearchTree(N);
           else Left->insert(N);
  else if (Right==NULL) Right = new intBinarySearchTree(N);
           else Right->insert(N);
} 

/* display() is a crude method for displaying a tree by traversing it in
infix order and indicated the depth by the degree of indentation.
display1 is a subroutine */

void display1(int INDENT)
{  if (Left != NULL) Left->display1(INDENT+1);
  for (int i=0; i<INDENT; i++) cout << "      ";
  cout << Key << "\n";
  if (Right!= NULL) Right->display1(INDENT+1);
}


void display() { display1(0); }

};  /* End of intBinarySearchTree */

  
int main() {
int A[5] = {5, 2, 20, 15, 8};
intBinarySearchTree Tree=intBinarySearchTree(10);

for (int i=0; i<5; i++) Tree.insert(A[i]);
Tree.display();
Tree.findAndReport(5);
Tree.findAndReport(6);
}