/**
* 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, int f, int l);
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
};