template <class T>
struct node{
  int key;
  T data;
  node* left;
  node* right;
  node(int k, T x): key(k), data(x), left(0), right(0) {}
};

template <class T>
class binarySearchTree{
public:
  binarySearchTree(): root(0) {
  //ARG:
  //DESC: root is initialized with 0.
  }
  ~binarySearchTree(){
  //ARG:
  //DESC: memory allocated for search tree is freed.
    _delete(root);
  }
  T* search(int k) const {
  //ARG:
  //DESC: return value is data item of a node with key == k,
  //      if such a node exists; otherwise it is 0.
    return search(root, k);
  }
  void insert(int k, T d){
   //ARG: binary search tree rooted at root (can be empty).
   //DESC: binary search tree contains node with key k
   //      and data item d.
    insert(root, k, d);
  }
  void insertAsRoot(int k, T d){
  //ARG: binary search tree rooted at root (can be empty).
  //DESC: binary search rooted at root. The node at the root
  //      has key k and data item d.
    insertAsRoot(root, k, d);
  }
  void remove(int k) {
  //ARG: binary rooted at root.
  //DESC: binary tree rooted at root from  which a node
  //      with key k has been removed.
    remove(root, k);
  }
  void inOrderWalk() const {
  //ARG: binary search tree rooted at root.
  //DESC: all keys stored in the tree are printed in
  //      increasing order on stdout.
    inOrderWalk(root);
  }
  int minKey() const {
  //ARG: non-empty binary search tree rooted at root.
  //DESC: the minimum key stored in the tree is returned.
    return minKey(root);
  }
  int maxKey() const {
  //ARG: non-empty binary search tree rooted at root.
  //DESC: the maximum key stored in the tree is returned.
    return maxKey(root);
  }
private:
  node<T>* root;
  void _delete(node<T>* p);
  T* search(node<T>* p, int k) const;
  void insert(node<T>* &p, int k, T d);
  void rotateRight(node<T>* p);
  void rotateLeft(node<T>* p);
  void insertAsRoot(node<T>* &p, int k, T d);
  void remove(node<T>* &p, int k);
  void inOrderWalk(node<T>* p) const;
  int minKey(node<T>* p) const;
  int maxKey(node<T>* p) const;
};

template <class T>
void binarySearchTree<T>::_delete(node<T>* p){
//ARG:
//DESC: memory allocated for tree rooted at p is freed.
  if(p != 0){
    _delete(p->left);
    _delete(p->right);
    delete p; 
  }
}

template <class T>
T* binarySearchTree<T>::search(node<T>* p, int k) const{
//ARG:
//DESC: return value is data item of a node with key == k,
//      if such a node exists; otherwise it is 0.
  if(p == 0) return 0;
  int kk = p->key;
  if(kk == k) return &(p->data);
  if(kk < k) return search(p->left, k);
  else return search(p->right, k);
}

template <class T>
void binarySearchTree<T>::insert(node<T>* &p, int k, T d){
//ARG: binary search tree rooted at p (can be empty).
//DESC: binary search tree rooted at p that contains node
//      with key k and data item d.
  if(p == 0)
    p = new node<T>(k ,d);
  else if(k < p->key) //convention, could also use <=
    insert(p->left, k, d);
  else
    insert(p->right, k, d);
}

template <class T>
void binarySearchTree<T>::rotateRight(node<T>* p){
//ARG: (1) p->left != 0
//     (2) binary search tree rooted at p.
//DESC: binary search tree rooted at p->left.
  node<T>* q = p->left;
  p->left = q->right;
  q->right = p;
  p = q;
}

template <class T>
void binarySearchTree<T>::rotateLeft(node<T>* p){
//ARG: (1) p->right != 0
//     (2) binary search tree rooted at p.
//DESC: binary search tree rooted at p->right.
  node<T>* q = p->right;
  p->right = q->left;
  q->left = p;
  p = q;
}

template <class T>
void binarySearchTree<T>::insertAsRoot(node<T>* &p, int k, T d){
//ARG: binary search tree rooted at p (can be empty).
//DESC: binary search rooted at p. The node pointed to
//      by p has key k and data item d.
  if(p == 0)
    p = new node<T>(k ,d);
  else if(k < p->key){ //convention; could also use <=
    insertAsRoot(p->left, k, d);
    rotateRight(p);
  } else{
    insert(p->right, k, d);
    rotateLeft(p);
  }
}

template <class T>
void binarySearchTree<T>::remove(node<T>* &p, int k){
//ARG: binary rooted at p.
//DESC: binary tree rooted at p from  which a node
//      with key k has been removed if there was one.
  if(p == 0) return;
  int kk = p->key;
  if(k < kk){
    remove(p->left, k);
    return;
  }
  if(k > kk){
    remove(p->right, k);
    return;
  }
  node<T>* q = p;
  node<T>* r = p->right;
  if(r == 0)
    p = p->left;
  else{
    while(r->left != 0)
      rotateRight(r);
    r->left = p->left;
    p = r;
  }
  delete q;
}

template <class T>
void binarySearchTree<T>::inOrderWalk(node<T>* p) const {
//ARG: binary search tree rooted at p.
//DESC: all keys stored in the tree rooted at p
//     are printed in increasing order on stdout.
  if(p != 0){
    inOrderWalk(p->left);
    std::cout << "[" << p->key << "]";
    inOrderWalk(p->right);
  }
}

template <class T>
int binarySearchTree<T>::minKey(node<T>* p) const {
//ARG: non-empty binary search tree rooted at p.
//DESC: the minimum key stored in the tree rooted
//      at p is returned.
  while(p->left != 0)
    p = p->left;
  return p->key;
}

template <class T>
int binarySearchTree<T>::maxKey(node<T>* p) const {
//ARG: non-empty binary search tree rooted at p.
//DESC: the maximum key stored in the tree rooted
//      at p is returned.
  while(p->right != 0)
    p = p->right;
  return p->key;
}