#ifndef BSTREE_H
#define BSTREE_H

#include <iostream>

//tree node
template<class T>
struct node{
node(const T &val) : data(val),left(NULL),right(NULL){}
T data;
node *left;
node *right;
};

//binay search tree
template<class T>
class BSTree{
public:
BSTree() : root(NULL){}

//copy control
~BSTree();
BSTree(const BSTree<T>&);
BSTree& operator= (const BSTree<T>&);
//member functions

void add(const T&); //add an element to the tree

void pre_print() const{pre_recursive(root);} //print the tree by pre order
void in_print() const{in_recursive(root);} //print the tree by in order
void post_print() const{post_recursive(root);} //print the tree by post order

void clear(){clr_recursive(root);root = NULL;} //delete all the nodes

bool empty() const{return root == NULL;}
int size() const{return size_recursive(root);} //count how many nodes
int height() const{return height_recursive(root);} //count the hight of a tree

node<T>* get_root() const {return root;}
protected:
//auxiliary functions
void pre_recursive(node<T>*) const;
void in_recursive(node<T>*) const;
void post_recursive(node<T>*) const;

void clr_recursive(node<T>*);
int size_recursive(node<T>*) const;
int height_recursive(node<T>*)const;
private:
//data member
node<T> *root;
};

template<class T>
BSTree<T>::~BSTree(){
clear();
}

template<class T>
void BSTree<T>::add(const T &val){
if (root == NULL)
root = new node<T>(val);
else{
node<T> *new_node = new node<T>(val);
node<T> *curr = root;
while (true){
if (val < curr->data){
if (curr->left == NULL){
curr->left = new_node;
break;
}
else
curr = curr->left;
}
else{
if (curr->right == NULL){
curr->right = new_node;
break;
}
else
curr = curr->right;
}
}
}
}

template<class T>
void BSTree<T>::pre_recursive(node<T> *pre_root) const{
if (pre_root){
std::cout << pre_root->data << " ";
pre_recursive(pre_root->left);
pre_recursive(pre_root->right);
}
}

template<class T>
void BSTree<T>::in_recursive(node<T> *in_root) const{
if (in_root){
in_recursive(in_root->left);
std::cout << in_root->data << " ";
in_recursive(in_root->right);
}
}

template<class T>
void BSTree<T>::post_recursive(node<T> *post_root) const{
if (post_root){
post_recursive(post_root->left);
post_recursive(post_root->right);
std::cout << post_root->data << " ";
}
}

template<class T>
void BSTree<T>::clr_recursive(node<T> *clr_root){
if (clr_root){
clr_recursive(clr_root->left);
clr_recursive(clr_root->right);
delete clr_root;
}
}

template<class T>
int BSTree<T>::size_recursive(node<T> *size_root) const{
if (size_root){
return size_recursive(size_root->left)
+ size_recursive(size_root->right)+1;
}
return 0;
}

template<class T>
int BSTree<T>::height_recursive(node<T> *height_root) const{
int lh,rh;
if (height_root){
lh = height_recursive(height_root->left);
rh = height_recursive(height_root->right);
return (lh > rh ? lh : rh) + 1;
}
return 0;
}

#endif