/***********************************************************************
* binarytree.h
*
* Header file for a simple inplementation of a binary tree
*
* Templates allow the tree to be used, without modification, for any
* type which can be compared using <, >, ==
*
* Note that there is no corresponding .cpp file. Templates must be
* implemented in a single file.
*
* Written by Paul Bonamy - 24 January 2010
* Modified to use templates - 19 March 2010
************************************************************************/

#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <iostream>

using namespace std;

/***********************************************************************
 * really, really simple node class.
 * Could be expanded with accessor methods, additional data, etc
 ***********************************************************************/
template <typename T> class Node {
// this ^ tells the compiler that this is a template, and we'll be
// receiving a type, named T, to be used throughout the class
    public:
        T value;      // value stored in the tree
        // Note the T. value will be of whatever type the user specifies
        Node<T> * left;    // left and right children of the node. 0 if no child.
        Node<T> * right;
        // The name of the template node class is now Node<T>
        Node<T>() { left = right = 0; } // default constructor. pretty trivial
};

/***********************************************************************
 * Simple-ish binary tree class.
 * Provides basic insert, remove, empty, and print
 ***********************************************************************/
template <typename T> class BinaryTree {
// this ^ tells the compiler that this is a template, and we'll be
// receiving a type, named T, to be used throughout the class
    private:
        // Node is also a templated class, so we have to define
        // what type it will be storing. That's what the <T> does.
        Node<T> * root;    // address of first node in the list
    
    public:
        BinaryTree();   // default constructor
        ~BinaryTree();  // destructor
        // Ts below to allow for the use of the user-specified type
        void insert(T v); // insert v into the tree
        void empty();   // delete all nodes in the tree
        void print();   // print contents of tree
        
        
        /*
         * Overloading friend functions is tricky.
         * You need them to be templates (obviously), but they
         * aren't directly aware of the type of the rest of the class.
         * Explicitely declare them templates with a different
         * typename to get around this.
         */
        template<typename U>
        friend ostream & operator<< (ostream & out, const BinaryTree<U>& b);
        
    private:
        // note that we still have to specify the type of the node
        void insert_helper(Node<T>* root, T v);  // Helper for the insert method
        void empty_helper(Node<T>* root);    // helper for the empty method
        void print_helper(Node<T>* root);    // print contents of the array
};


/***********************************************************************
 * template <typename T> BinaryTree<T>::BinaryTree()
 *
 * default constructor for the BinaryTree class.
 * Only needs to initialize head to 0
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> BinaryTree<T>::BinaryTree() {
// This ^ and the angle brackets ^ are required for member functions
// of templated classes
    root = 0; // set head to 0 aka NULL, so we can detect empty tree
    return;
}

/***********************************************************************
 * template <typename T> BinaryTree<T>::~BinaryTree()
 *
 * destructor for the BinaryTree class.
 * Delete all nodes in the tree and return
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> BinaryTree<T>::~BinaryTree() {
    empty(); // we could code the delete here, but let's use empty()
    return;
}

/***********************************************************************
 * template <typename T> void BinaryTree<T>::insert(T v)
 *
 * Insert a given value into the tree. We rely on a private,
 * recursive helper to make this easier.
 *
 * v -> value to add to tree / no return
 ***********************************************************************/
template <typename T> void BinaryTree<T>::insert(T v) {
    // Note that the input parameter is of type T
    if (root == 0) {
        // the tree is empty, so we use this value to create a root node
        root = new Node<T>; // We need to give the node a type
        root->value = v;
    }
    else {
        // the tree is non-empty, so we'll need to do more work
        insert_helper(root, v);
    }
    
    return;
    
}
/***********************************************************************
 * template <typename T> void BinaryTree<T>::empty()
 *
 * Delete all nodes in the tree and return. Relies on a private,
 * recursive helper to make this easier.
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> void BinaryTree<T>::empty() {
    empty_helper(root); // call the recursive emptier, starting at root
    root = 0;           // note that we emptied the tree
    return;
}

/***********************************************************************
 * template <typename T> void BinaryTree<T>::print()
 *
 * Print the contents of all nodes using in-order traversal. Relies
 * on a private, recursive helper for ease of use.
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> void BinaryTree<T>::print() {
    if( root == 0) {
        cout << "empty" << endl;    // tree is empty, so say so
    }
    else {
        print_helper(root); // call the recursive printer, starting at root
        cout << endl;       // print out an endl when we're done printing
    }

    return;
}

/***********************************************************************
 * template <typename T> void BinaryTree<T>::insert_helper(Node<T>* curr, T v)
 *
 * Recursively traverses through the tree, looking for the right
 * place to insert the new value.
 *
 * curr -> current node under examination. Start with root
 * v -> value to add to tree
 * no return
 ***********************************************************************/
template <typename T> void BinaryTree<T>::insert_helper(Node<T>* curr, T v) {
    if (v < curr -> value) {
        // we need to insert to the left of the current node
        if (curr -> left == 0) {
            // there is no left child, so create one with this value
            curr -> left = new Node<T>; // Specify the node's type
            curr -> left -> value = v;
        }
        else {
            // there is a left child, so search from there
            insert_helper(curr -> left, v);
        }
    }
    else if (curr -> value == v) {
        // the current node has the goal value, so do nothing. we're done
    }
    else {
        // we must need to insert to the right of the current node
        if( curr -> right == 0) {
            // there is no right child, so create one with this value
            curr -> right = new Node<T>;
            curr -> right -> value = v;
        }
        else {
            // there is a right child, so search from there
            insert_helper(curr -> right, v);
        }
    }
    return;
}

/***********************************************************************
 * template <typename T> void BinaryTree<T>::empty_helper(Node<T>* curr)
 *
 * Perform a post-order traversal, deleting each node once its
 * children have been deleted.
 *
 * curr -> current node under examination / no return
 ***********************************************************************/
template <typename T> void BinaryTree<T>::empty_helper(Node<T>* curr) {
    if (curr == 0) return;          // stop if we ran out of tree
    empty_helper(curr -> left);     // delete left children
    empty_helper(curr -> right);    // delete right children
    delete curr;                    // delete me
    return;
}

/***********************************************************************
 * template <typename T> void BinaryTree<T>::print_helper(Node<T>* curr)
 *
 * Do an in-order traversal of the tree, printing node values
 * as we go
 *
 * curr -> current node under examination / no return
 ***********************************************************************/
template <typename T> void BinaryTree<T>::print_helper(Node<T>* curr) {
    if (curr == 0) return;          // stop if we ran out of tree
    print_helper(curr -> left);     // print left children
    cout << curr -> value << " ";   // print me
    print_helper(curr -> right);    // print right children
    return;
}

/***********************************************************************
 * template <typename U> ostream & operator<< (ostream & out, const LinkedList<U>& l)
 *
 * Print a simple status of the tree using <<
 *
 * no parameters / no return
 ***********************************************************************/
// Note that the typename associated with the class itself (T) doesn't
// appear in this function. Instead, we use the special other typename,
// U, anywhere we might expect to see a T
template<typename U> ostream & operator<< (ostream & out, const BinaryTree<U>& b) {
    if( b.root == 0) {
        cout << "empty" << endl;    // tree is empty, so say so
    }
    else {
        cout << "non-empty" << endl; // tree is non-empty
    }
    return out;
}

#endif