/**
 * Binary Search Tree class
 *
 * * Each node in the class has a value
 * * The left subtree of a node contains only values less than the node's value.
 * * The right subtree of a node contains only values greater than the node's value.
 * * Left subtree and right subtree are both binary search trees.a
 * * A total order is defined on these values (pre, in or post order)
 *
 **
 */

using namespace std;
typdef class BinarySearchTree * tree;

class BinarySearchTree
{
	private:
		int key;
		int pos;	//Number of nodes visited before N in inorder travesel of bst.
		int depth;	//Depth of N in the tree.
		BinarySearchTree *left;
		BinarySearchTree *right;

	public:
		BinarySearchTree();		//Pre : none
						//Post: an empty bst is created

		BinarySearchTree(int k);	//Pre : k<=100
						//Post: A binary search tree with
						//key = k, left = NULL and right
						//= NULL is created.

		void insert(int k, tree &t, int depth);
						//Pre : k<=100
						//Post: new bst is created for k
						//and then inserted into t
						//in correct position.

		int getKey();			//Pre : none
						//Post: returns key of bst

		int getPos();			//Pre : none
						//Post: returns pos of bst

		int getDepth();			//Pre : none
						//Post: returns depth of bst

		void setPos(int p);		//Pre : 
						//Post: sets pos in bst
		
		void setDepth(int d);		//Pre : 
						//Post: sets depth in bst
	
};