/* binary search tree */
using namespace std;
#include<iostream>

template <typename T>
class comparator
{
public:
  int dir;
  virtual bool le(T a, T b);
  virtual bool eq(T a, T b);  
  comparator() { dir = 0; }
  comparator(int d) {dir=d;}
};


template <typename ST>
class node
{
public:
  ST head;
  node<ST> *left;
  node<ST> *right;
  static comparator<ST> *comp;  // static so it's shared by all instances.
                                // value to be set externally.

  node(ST h, node<ST> *l, node<ST> *r)
  { head=h;  left=l;  right=r; }
  node(ST h)
  { head = h; left=NULL; right=NULL; }
  ~node()
  {
    if (left!=NULL) delete(left);
    if (right!=NULL) delete(right);
  }

  // computes height:
  virtual int height()
  {
    int ch = 0; // height of longer sub-branch
    if (left!=NULL) ch = left->height();
    if (right!=NULL)
      {
	int rh = right->height();
	if (rh>ch) ch = rh;
      }
    return ch+1;
  }

  // insert a new node
  virtual void insert(ST x)
  {
    if (comp->le(head,x)) // go right
      {
	if (right!=NULL) right->insert(x);
	else right = new node(x);
      }
    else
      {
	if (left!=NULL) left->insert(x);
	else left = new node(x);
      }    
  }  

  // finds and deletes largest node on left subtree - returns that node
  static node<ST>* cutright(node<ST> * n)
  {
    node<ST> *i, *p, *t; // current, parent, and swap pointers
    if (n==NULL) return NULL;
    *p = NULL;
    *i =n;
    while (i->right!=NULL) { t=i; i=i->right; p = t; }
    p->right = NULL;
    return i;
  }

  static node<ST> * cutleft(node<ST> * n)
  {
    node<ST> *i, *p, *t;
    if (n==NULL) return NULL;
    *p = NULL;
    *i =n;
    while (i->left!=NULL) { t=i; i=i->left; p = t; }
    p->left = NULL;
    return i;
  }

  virtual node<ST> * deletenode(ST x)
  {
    node<ST> *p, *i;  // two pointers, previous and current
    node<ST> *temp; 
    i = this;
    p = NULL;
    char flag = 0;  // 0 for left, 1 for right;
    while (i!=NULL && flag<2)
      {
	if (comp->le(x,i->head))  // go left
	  {
	    temp = i; i=i->left; p=temp;  
	    flag = 0;
	  }
	else if (comp->le(i->head,x))  // go right
	  {
	    temp = i; i=i->right; p = temp;
	    flag = 1;
	  }
	else // delete i node
	  {
	    if (p==NULL) return NULL; // special case: one node
            node * r = NULL; // replacement node
	    if (left != NULL) r = cutright(i->left);
	    else if (right!=NULL) r = cutleft(i->right);
	    if (flag==0) p->left=r; else p->right=r;
            flag = 2;  // stops loop
	  }
      } // while
    return i;
  } // delete

};  // class node