#ifndef BST_H
#define BST_H

#include "BSTNode.h"

// Binary Search Tree
// BST class is a friend of BSTNode so BSTNode private members are
// directly accessible in BST class.
template <class T>
class BST {
	private:
		BSTNode<T> *root;
		// internal implementation
		BSTNode<T> *insert(BSTNode<T> *r, T data);
		void inOrder(BSTNode<T> *r, void (*visit)(T));
		bool search(BSTNode<T> *r, T data);
		bool remove(BSTNode<T> **r, T data);
		void deleteNode(BSTNode<T> **r);
	public:
		BST();
		~BST();
		// user interface
		void insert(T data);
		void inOrder( void (*visit)(T) );
		bool search(T data);
		bool remove(T data);

		int getNodeCount(); // This function returns the number of nodes in the tree. 
		int getLeafCount(); // This function returns the number of leaf nodes in the tree.
		int getTreeHeight();// This function returns the height of the tree.


};

// constructor
template <class T>
BST<T>::BST() {
	root = 0;
}

template <class T>
BST<T>::~BST() {
}

template <class T>
void BST<T>::insert(T data) {
	root = insert(root, data); // private 'insert' member function
}

// data is insert into the BST such that the BST properties are preserved.
template <class T>
BSTNode<T> *BST<T>::insert(BSTNode<T> *rt, T data) {
	if (rt == 0) {
		// tree is empty
		rt = new BSTNode<T>(data);
	} else {
		if (data < rt->data) {
			// insert into the left subtree
			rt->left = insert(rt->left, data);
		} else if (data > rt->data) {
			// insert into the right subtree
			rt->right = insert(rt->right, data);
		} // ignore duplicates
	}

	return rt;
}

template <class T>
void BST<T>::inOrder(void (*visit)(T) ) {
	inOrder(root, visit);
}

template <class T>
void BST<T>::inOrder(BSTNode<T> *rt, void (*visit)(T)) {
	if (rt != 0) {
		inOrder(rt->left, visit);
		visit(rt->data);
		inOrder(rt->right, visit);
	}
}

// public: search data in the BST
template <class T>
bool BST<T>::search(T data) {
	return search(root, data);
}

// private: search data in the BST with rt as root
template <class T>
bool BST<T>::search(BSTNode<T> *rt, T data) {
	if (rt == 0) return false;
	else if (rt->data == data) return true;
	else if (data < rt->data) return search(rt->left, data);
	else return search(rt->right, data);
}

// public: delete the node with data from the BST
template <class T>
bool BST<T>::remove(T data) {
  return remove(&root, data);
}

// private: delete a node with data from BST with rt as root
template <class T>
bool BST<T>::remove(BSTNode<T> **rt, T data) {
	if (*rt == 0) return false;
	else if (data == (*rt)->data) {
		deleteNode(rt);
		return true;
	} else if (data < (*rt)->data) {
		return remove(&((*rt)->left), data);
	} else { // data > (*rt)->data
		return remove(&((*rt)->right), data);
	}
}

// private: node 'node' is deleted from the BST.
// Resultant smaller BST retains properties of BST.
template <class T>
void BST<T>::deleteNode(BSTNode<T> **node) {
	BSTNode<T> *r = *node;
	if (r->right == 0) {
		*node = r->left; // reattach left subtree
		delete r;
	} else if (r->left == 0) {
		*node = r->right; // reattach right subtree
		delete r;
	} else {
		BSTNode<T> *q;
		// find left most node of right subtree
		for (q = r->right; q->left != 0; q = q->left) ;
		q->left = r->left; // reattach left subtree
		*node = r->right;
		delete r;
	}


}

template <class T>
int BST<T>::


#endif