#include <iostream>

using namespace std;

/* binarySearchTree generalized the code for binary search trees in 
intBinarySearchTree.cpp by allowing the values to be of arbitrary type.
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.) */

template <typename T>
class binarySearchTree {
protected: T Key;  
           binarySearchTree *Left, *Right;
  /* protected members are visible in derived classes */

public: binarySearchTree(T N): /* Construct leaf with value N*/
  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(T 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(T 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.

The value returned is meaningless, but the method has to be declared as 
returning value of type int since when we overwrite it, we will want a value.
This is a limitation of the overwrite system. */

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

/* 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 binarySearchTree */

  
int main() {
int I[8] = {5, 2, 20, 5, 15, 8, 20};
float F[8] = {5.2, 2.2, 20.2, 5.2, 15.2, 8.2, 20.2};
binarySearchTree<int> ITree=binarySearchTree<int>(10);
binarySearchTree<float> FTree=binarySearchTree<float>(10.2);

for (int i=0; i<6; i++) ITree.insert(I[i]);
for (int i=0; i<6; i++) FTree.insert(F[i]);
ITree.display();
ITree.findAndReport(5);
ITree.findAndReport(6);
cout << "\n\n";
FTree.display();
FTree.findAndReport(5.2);
FTree.findAndReport(6.2);
}