// Binary Search Tree interface
#ifndef _BST_H
#define _BST_H

#include<vector>
#include<iostream>

using namespace std;

/* Binary search tree class 
 */

template<class T>
class BST {
 public:
    BST(); // create an empty binary search tree
    BST(const BST& src); // copy constructor
    ~BST(); // destructor
    const BST& operator=(const BST& src); // copy assignment operator

    void add(const T& value); // add value to binary search tree
    T getMin() const; // return smallest value in the binary search tree
    bool isEmpty() const;  // return true if the binary search tree is empty, false otherwise
    bool contains(const T& value) const;  // return true if value is in the tree, false otherwise
    
    void remove(const T& value);  // if value is in the tree, remove it
    int size() const; // return number of nodes in tree
    int getHeight() const; // return height of tree
    vector<T> inOrder() const; // add tree's node values to a vector during an inorder traversal
    vector<T> preOrder() const; // add tree's node values to a vector during a preorder traversal
    vector<T> postOrder() const; // add tree's node values to a vector during a postorder traversal
    bool inTree(const T& value) const; // return true if value is in the tree, and false otherwise
    
    

 private:
    
    struct TreeNode {
	T data;
	TreeNode* right;
	TreeNode* left;
	TreeNode(T d, TreeNode* r = NULL, TreeNode* l = NULL) {
	    data = d; right = r; left = l;
	}
    };
   
    
    TreeNode* root;

    /* Helper functions */
    void add(TreeNode* node, const T& value);
    T getMin(TreeNode* node) const;
    bool contains(TreeNode* node, const T& value) const;
    void remove(TreeNode*& node, const T& value);
    void destroy(TreeNode* node);
    void inOrder(TreeNode* node, vector<T>& result) const;
    void preOrder(TreeNode* node, vector<T>& result) const;
    void postOrder(TreeNode* node, vector<T>& result)const;
    int size(TreeNode* node) const;
    int getHeight(TreeNode* node) const;

    // Make a deep copy of the tree rooted at originalTree. Helper for copy assignment operator and
    // copy constructor. 
    void copyTree(TreeNode*& copy, const TreeNode* originalTree); 
};

template<class T>
bool BST<T>::inTree(const T& value) const {
    // YOUR CODE GOES HERE
    
}

template<class T>
BST<T>::BST() {
    // YOUR CODE GOES HERE
}

template<class T>
void BST<T>::add(const T& value) {
    // YOUR CODE GOES HERE
}

template<class T>
void BST<T>::add(TreeNode* node, const T& value) {
    // YOUR CODE GOES HERE
}

template<class T>
T BST<T>::getMin() const {
    // YOUR CODE GOES HERE
}

template<class T>
T BST<T>::getMin(TreeNode* node) const {
    // YOUR CODE GOES HERE
}

template<class T>
bool BST<T>::contains(const T& value) const {
    // YOUR CODE GOES HERE
}

template<class T>
bool BST<T>::contains(TreeNode* node, const T& value) const {
    // YOUR CODE GOES HERE
}

template<class T>
void BST<T>::remove(const T& value) {
    // YOUR CODE GOES HERE
}

template<class T>
void BST<T>::remove(TreeNode*& node, const T& value) {
    // YOUR CODE GOES HERE
}

template<class T>
BST<T>::~BST() {
    // YOUR CODE GOES HERE
}



template<class T>
void BST<T>::destroy(TreeNode* node) {
    // YOUR CODE GOES HERE
}

template<class T>
bool BST<T>::isEmpty() const {
    // YOUR CODE GOES HERE
}


// copy assignment operator
template<class T>
const BST<T>& BST<T>::operator=(const BST& rhs) {
    // YOUR CODE GOES HERE
}


// copy constructor
template<class T>
BST<T>::BST(const BST& rhs) {
    // YOUR CODE GOES HERE
}

template<class T>
vector<T> BST<T>::inOrder() const {
    // YOUR CODE GOES HERE
}

template<class T>
void BST<T>::inOrder(TreeNode* node, vector<T>& result)const {
    // YOUR CODE GOES HERE
}

template<class T>
vector<T> BST<T>::preOrder() const{
    // YOUR CODE GOES HERE

}

template<class T>
void BST<T>::preOrder(TreeNode* node, vector<T>& result)const {
    // YOUR CODE GOES HERE
}

template<class T>
vector<T> BST<T>::postOrder() const{
    // YOUR CODE GOES HERE
}

template<class T>
void BST<T>::postOrder(TreeNode* node, vector<T>& result) const{
    // YOUR CODE GOES HERE
}

template<class T>
int BST<T>::size() const {
    // YOUR CODE GOES HERE
}

template<class T>
int BST<T>::size(TreeNode* node) const {
    // YOUR CODE GOES HERE
}

template<class T>
int BST<T>::getHeight() const {
    // YOUR CODE GOES HERE
}

template<class T>
int BST<T>::getHeight(TreeNode* node) const{
    // YOUR CODE GOES HERE
}

template<class T>
void BST<T>::copyTree(TreeNode*& copy, const TreeNode* originalTree) {
    // YOUR CODE GOES HERE
}

#endif