#include <iostream>

using namespace std;

/* binarySearchTree generalized the code for binary search trees in 
sizedBinarySearchTree.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 */

/* class sizedBinarySearchTree defines a sized binary search as an extension
of binarySearchTree, adding a "Size" field to each node that records the
size of each subtree. */

template <typename T>
class sizedBinarySearchTree: public binarySearchTree<T> {
protected: int Size;
           

/* The constructor calls the constructor for binarySearchTree and 
initializes Size to be 1.  Note: if binarySearchTree included a 
constructor with no arguments (a default constructor) then that call
could be omitted (left implicit) */

public: sizedBinarySearchTree(T N): /* Construct leaf */
  binarySearchTree<T>(N),  Size(1) {  }

/* The modified insert method adjusts the size of every node traversed
on the path to the new node. insert(N) returns 1 if N was added to the tree
and 0 if N was already present in the tree */

/* "Member fields of a base class in a derived template must be accessed using
'this'" -- why, I do not know. 
See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19189
Thanks to Paul Bethe for alerting me to this. */

int insert(T N)
{ int added = 1;
  if (this->Key == N) added=0;
  else if (N < this->Key) 
         if (this->Left==NULL) this->Left = new sizedBinarySearchTree(N);
           else added = static_cast<sizedBinarySearchTree<T>*>
                                             (this->Left)->insert(N);
/* The static cast is neeeded here and below because "Left" and "Right"
are declared of type binarySearchTree* and you have to tell the compiler
that they are actually of type sizedBinarySearchTree*.  Otherwise, this
recursive call will get the insert method defined for binarySearchTree.
Thanks to Paul Bethe for showing me this C++ construction. */
  else if (this->Right==NULL) this->Right = new sizedBinarySearchTree(N);
           else added = static_cast<sizedBinarySearchTree<T>*>
                                          (this->Right)->insert(N);

  Size += added;
  return(added);
} 

/* Modify display1 by having it print out the sizes as well as the values */
void display1(int INDENT)
{  if (this->Left != NULL) 
      static_cast<sizedBinarySearchTree<T>*>(this->Left)->display1(INDENT+1);
  for (int i=0; i<INDENT; i++) cout << "         ";
  cout << this->Key << "[" << Size << "]\n";
  if (this->Right!= NULL) 
      static_cast<sizedBinarySearchTree<T>*>(this->Right)->display1(INDENT+1);
}

void display() { display1(0); } 


};  /* End of sizedBinarySearchTree */
  
int main() {
int A[8] = {5, 2, 20, 5, 15, 8, 20};
float B[8] = {5.2, 2.2, 20.2, 5.2, 15.2, 8.2, 20.2};
binarySearchTree<int> Tree=binarySearchTree<int>(10);
sizedBinarySearchTree<float> STree=sizedBinarySearchTree<float>(10.2);

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

cout << "\n Sized tree:\n";
STree.display();
STree.findAndReport(5.2);
STree.findAndReport(6.2);
}