#include <iostream>
#include "my_bst.h"
using namespace std;
 
int main()
{
	my_bst<int,int> ab;
	ab.insert(5,10);
	return 0;
}

#ifndef MY_BST_NODE_H
#define MY_BST_NODE_H
 
#include <iostream>
 
using namespace std;
 
template<class KT,class DT>
class my_bst_node
{
public:
	inline my_bst_node()
	{
		left=right=0;
	}
	inline my_bst_node(KT tag,DT info, my_bst_node * l=0, my_bst_node * r=0)
	{
		key=tag;
		data=info;
		left=l; 
		right=r;
	}
 
	KT key;
	DT data;
	my_bst_node * left;
	my_bst_node * right;
};
 
#endif

#ifndef MY_BST_H
#define MY_BST_H
#include <iostream>
#include "my_bst_node.h"
 
using  namespace std;
 
template<class KT,class DT>
class my_bst
{
public:
	//default constructor
	my_bst();
 
	//inserts a new node into binary tree
	void insert(KT searchkey, const DT &newDataItem);
 
	//
	bool search(KT searchkey);
 
	//delete node based on which key you want to delete
	void delet(KT searchkey);
 
	//
	DT preorder_display(KT searchkey);
 
	//
	DT inorder_display(KT searchkey);
 
	//
	DT postorder_display(KT searchkey);
 
	//returns height of BST
	int height() const;
 
	//
	bool balanced() const;
 
	//
	void show_bst_structure() const;
 
private:
	my_bst_node<KT,DT>* root;
 
	void insert_sub(my_bst_node<KT,DT>*& root, KT searchkey, const DT & newDataItem);
 
	int getHeightSub(my_bst_node<DT,KT> * p);
};
 
template <class KT, class DT>
my_bst<KT,DT>::my_bst(void)
{
	root=0;
}
 
template <class KT, class DT>
void my_bst<KT,DT>::insert(KT searchkey, const DT &newDataItem)
{
	insert_sub(root, searchkey, newDataItem);
}
 
template <class KT, class DT>
void my_bst<KT,DT>::insert_sub(my_bst_node<KT,DT>*& root, KT searchkey, const DT &newDataItem)
{
   //if empty tree
   if(root=NULL)
   {
       root=new my_bst_node<KT,DT>(searchkey, newDataItem);
   }
   //key less than root nodes 
   else if(searchkey<root->key)
   {
       insert_sub(root->left, searchkey, newDataItem);
   }
   //key greater than root nodes
   else
   {
       insert_sub(root->right, searchkey, newDataItem);
   }
}
#endif