#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 {
protected: int Key;  
           intBinarySearchTree *Left, *Right;
  /* protected members are visible in derived classes */

public: intBinarySearchTree(int 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(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.

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(int N)
{ if (Key == N) return(0) ;
  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);
  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 intBinarySearchTree */

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

class sizedBinarySearchTree: public intBinarySearchTree {
protected: int Size;
           

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

public: sizedBinarySearchTree(int N): /* Construct leaf */
  intBinarySearchTree(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 */

int insert(int N)
{ int added = 1;
  if (Key == N) added=0;
  else if (N < Key) 
         if (Left==NULL) Left = new sizedBinarySearchTree(N);
           else added = static_cast<sizedBinarySearchTree*>(Left)->insert(N);
/* The static cast is neeeded here and below because "Left" and "Right"
are declared of type intBinarySearchTree* 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 intBinarySearchTree.
Thanks to Paul Bethe for showing me this C++ construction. */
  else if (Right==NULL) Right = new sizedBinarySearchTree(N);
           else added = static_cast<sizedBinarySearchTree*>(Left)->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 (Left != NULL) 
      static_cast<sizedBinarySearchTree*>(Left)->display1(INDENT+1);
  for (int i=0; i<INDENT; i++) cout << "         ";
  cout << Key << "[" << Size << "]\n";
  if (Right!= NULL) 
      static_cast<sizedBinarySearchTree*>(Right)->display1(INDENT+1);
}

void display() { display1(0); } 


};  /* End of sizedBinarySearchTree */
  
int main() {
int A[8] = {5, 2, 20, 5, 15, 8, 20};
intBinarySearchTree Tree=intBinarySearchTree(10);
sizedBinarySearchTree STree=sizedBinarySearchTree(10);

for (int i=0; i<6; i++) Tree.insert(A[i]);
for (int i=0; i<6; i++) STree.insert(A[i]);
Tree.display();
Tree.findAndReport(5);
Tree.findAndReport(6);
cout << "\n Sized tree:\n";
STree.display();
STree.findAndReport(5);
STree.findAndReport(6);
}