BST Functions:

Do not implement a class yet. We need these functions to be able to easily implement multiple classes.

First, let's design a tree_node structure:

In addition to the usual item, left, and right, we need to keep track of the "balance factor". 
balance factor is calculated as the height of the left subtree minus the height of the right subtree.
But we do not want to be calculating the height of left and right subtrees (by counting the nodes all the way down to the leaves) every time we need the balance factor. So, we need to keep track of the heights "on the fly" by updating the height (by looking at the heights of the left and right children) each time insertion and deletions are made. We can easily calculate the balance factor by subtracting the height of the right child from the height of the left child.

Do not simply increment (or decrement) the height after an insertion (or deletion.) This will not work.

template <typename T>
struct tree_node{
    T _item;
    tree_node<T>* _left;
    tree_node<T>* _right;
    int _height;
    int balance_factor(){
        //balance factor = height of the left subtree 
        //                        - the height of the right subtree
        //a NULL child has a height of -1
        //a leaf has a height of 0
    }

    int height(){
        // Height of a node is 1 + height of the "taller" child
        //A leaf node has a height of zero: 1 + max(-1,-1)
    }
    int update_height(){
        //set the _height member variable (call height();)
    }

    tree_node(T item=T(), tree_node* left=NULL, 
                          tree_node* right=NULL):
                    _item(item), _left(left), _right(right)
    {

        //don't forget to set the _height.
    }
    friend ostream& operator <<(ostream& outs, 
                                const tree_node<T>& t_node){
        outs<<"|"<<t_node._item<<"|";
    }
};

Implement the following functions for a Binary Search Tree:

template <typename T>
void tree_insert(tree_node<T>* &root, const T& insert_me);

template <typename T>
tree_node<T>* tree_search(tree_node<T>* root, const T& target);
template <typename T>
bool tree_search(tree_node<T>* root, const T& target,
                 tree_node<T>* &found_ptr);

template<typename T>
void tree_print(tree_node<T>* root, int depth=0,
                                    ostream& outs=cout);

template<typename T> //prints detailes info about each node
void tree_print_debug(tree_node<T>* root, int depth=0,
                                          ostream& outs=cout);

template <typename T> //clear the tree
void tree_clear(tree_node<T>* &root);

template <typename T> //erase target from the tree
bool tree_erase(tree_node<T>*& root, const T& target);
template <typename T> //erase rightmost node from the tree -> max_value
void tree_remove_max(tree_node<T>* &root, T& max_value);


template <typename T> //print in_order
void in_order(tree_node<T>* root,ostream& outs=cout);

template <typename T> //print pre_order
void  pre_order(tree_node<T>* root,ostream& outs=cout);

template <typename T> //print post_order
void  post_order(tree_node<T>* root,ostream& outs=cout);

template <typename T> //string in_order
string in_order_string(tree_node<T>* root);

template <typename T> //string pre_order
string pre_order_string(tree_node<T>* root);

template <typename T> //string post_order
string post_order_string(tree_node<T>* root);


template <typename T> //return copy of tree pointed to by root
tree_node<T>* tree_copy(tree_node<T>* root);

template <typename T> //Add tree src to dest
void tree_add(tree_node<T>* & dest, const tree_node<T>* src);

template <typename T> //sorted array of ints -> tree
tree_node<T>* tree_from_sorted_list(const T* a);

template <typename T> // sorted array -> tree
tree_node<T>* tree_from_sorted_list(const T* a, int size);

Testing:

You will write individual functions that will test every aspect of these. The insertion, the deletion, the copying and clearing and of course searching.