/**
 * 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)
 *
 **
 */
#include <vector>
using namespace std;
typedef 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;
	
	protected:

		vector<vector <int> > postOrder;
		vector<vector <int> > preOrder;
		vector<vector <int> > inOrder;

		vector<vector <int> >::iterator postOrderIterator;
		vector<vector <int> >::iterator preOrderIterator;
		vector<vector <int> >::iterator inOrderIterator;


	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.

		~BinarySearchTree();

		void draw(tree t, bool endline);
						//Pre : 
						//Post: Draws t

		void setInOrderPos(tree t, int &count);
						//Pre :
						//Post: Sets correct pos value
						//for all bsts

		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.
						//

		BinarySearchTree balance(tree t);
		BinarySearchTree balanceVector(vector< vector<int> > v);

		vector<int> nextPostOrder();		

		void serialisePostOrder(tree t);//HERE

		vector<int> nextPreOrder();

		void serialisePreOrder(tree t);//HERE

		vector<int> nextInOrder();

		void serialiseInOrder(tree t);//HERE
	
		int getSize(tree t);	

		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
	
};