#ifndef TREE_H
#define TREE_H

template <class T>
class BinTree;

template <class T>
class BinNode
{
   public:
   	friend class BinTree<T>;
	   T value;
	   BinNode<T>* left;
	   BinNode<T>* right;

	   inline BinNode(T val){left=NULL; right=NULL; value=val;};
			//constructor for BinNode
};

template <class T>
class BinTree
{
   BinNode<T>* root;
   public:
      enum {NOT_FOUND=-3, NO_MEM=-2, DUP_VAL=-1};
      static const int OK = 0;
      static const int DUPLICATE = -3;

      inline BinTree() {root=NULL;};
      	//default constructor for BinTree, inits head to NULL

      inline BinTree(const BinTree<T> &rhs) {this->root=zcopy(rhs.root);};
      	//copy constructor for BinTree

      void clear(void);
      	//deletes everything in tree and returns it to memory

      virtual int insert(T value);
      	//inserts 'value' into tree while keeping the tree a valid bin-search tree

      int remove(T value);
      	//removes 'vaue' from tree if found. Returns OK if found, or NOT_FOUND for
         //a missing value

      inline int height(void) const {return zclimb(this->root);};
      	//returns height of tree via a recursive function

      inline int size(void) const {return zsize(this->root);};
      	//returns size of tree via a recursive function

      inline void print_pre(void) const {zrint_pre(this->root);};
      void zrint_pre(const BinNode<T>* finger) const;
      	//prints all elements in tree in pre-order format
         //to use, call print_pre function.

      inline void print_in(void) const {zrint_in(this->root);};
      void zrint_in(const BinNode<T>* finger) const;
      	//prints all elements in tree in in-order format
         //to use, call print_in function.

      inline void print_post(void) const {zrint_post(this->root);};
      void zrint_post(const BinNode<T>* finger) const;
      	//prints all elements in tree in post-order format
         //to use, call print_post function.

      virtual inline BinTree<T>& operator = (const BinTree<T> &rhs){ this->root=zcopy(rhs.root); return *this;};
      	//copy constructor for BinTree

      int w_find(const T &target);
      	//searches for a particular target, and returns the number of comparisons
         //needed to locate said item  **does not check against nonexistent data

      void build(const usermaster &allusers);
      	//inserts all of the entry types from usermaster structure into a binary tree

      int itercount(const usermaster &allusers);
      	//performs a w_find on all entries in allusers and returns the sum of those searches

      virtual ~BinTree();
      	//destructor

   private:
      BinNode<T>* zcopy(const BinNode<T>*) const;
			//Use: makes a clone of tree in memory
         //Args: pointer to head of target tree
			//Returns: pointer to head of tree
			//Notes: called by copy constructor and operator=

      void zkill(BinNode<T>*);
			//Use: deletes subtrees, followed by self
			//Args: pointer to head of target tree
			//Notes: called by destructor

      int zclimb(const BinNode<T>*) const;
			//Use: recursive function for counting up height of tree
			//Args: pointer to head of target tree
			//Returns: height of longest branch

      int zsize(const BinNode<T>*) const;
			//Use: recursive function for counting up nodes in tree
			//Args: pointer to head of target tree
			//Returns: total node count from here below
};

#include "bintree.cpp"

#endif