//************************ BST.h **************************
//    simplified version of text binary search tree

#include <iostream>

using namespace std;

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

template<class T>
class BSTNode {
public:
  BSTNode() { 
    left = right = 0; 
  }
  BSTNode(const T& el, BSTNode *l = 0, BSTNode *r = 0) {
    key = el; left = l; right = r; 
  }
  T key;
  BSTNode *left, *right;
};

template<class T>
class BST {
public:
  BST() { 
    root = 0; 
  }
  ~BST() { 
    clear();
  }
  void clear() {
    clear(root); root = 0;
  }
  bool isEmpty() const { 
    return root == 0; 
  }
  void snapShot(ostream& out) {
   out << "TreeForm[";
   snapShot(out,root);
   out << ']' << endl;
  }
  void preorder() { 
    preorder(root);  
  }
  void inorder() { 
    inorder(root); 
  }
  void postorder() { 
    postorder(root); 
  }
  void insert(const T&);
  T* search(const T& el) const { 
    return search(root,el);
  }
  void deleteByCopying(BSTNode<T>*&);
  void findAndDeleteByCopying(const T&);
  void deleteByMerging(BSTNode<T>*&);
  void findAndDeleteByMerging(const T&);
protected:
  BSTNode<T>* root;
  void clear(BSTNode<T>*);
  T* search(BSTNode<T>*, const T&) const;
  void preorder(BSTNode<T>*);
  void inorder(BSTNode<T>*);
  void postorder(BSTNode<T>*);
  void snapShot(ostream& out,BSTNode<T>*);
  void visit(BSTNode<T>* p) { 
    cout << p->key << ' '; 
  }
};

template<class T>
void BST<T>::clear(BSTNode<T> *p) {
  if (p != 0) {
     clear(p->left);
     clear(p->right);
     delete p;
   }
}

template<class T>
void BST<T>::insert(const T& el) {  
  BSTNode<T> *p = root, *prev = 0;
  while (p != 0) {    // find a place for inserting new node;
    prev = p;
    if (p->key < el)
       p = p->right;
    else p = p->left;
  }
  if (root == 0)  // tree is empty;
     root = new BSTNode<T>(el);
  else if (prev->key < el)
     prev->right = new BSTNode<T>(el);
  else prev->left = new BSTNode<T>(el);
}

template<class T>
T* BST<T>::search(BSTNode<T>* p, const T& el) const {
  while (p != 0)
    if (el == p->key)
       return &p->key;
    else if (el < p->key)
       p = p->left;
    else p = p->right;
  return 0;
}

template<class T>
void BST<T>::inorder(BSTNode<T> *p) {
   if (p != 0) {
     inorder(p->left);
     visit(p);
     inorder(p->right);
   }
}

template<class T>
void BST<T>::preorder(BSTNode<T> *p) {
  if (p != 0) {
    visit(p);
    preorder(p->left);
    preorder(p->right);
  }
}

template<class T>
void BST<T>::postorder(BSTNode<T>* p) {
  if (p != 0) {
    postorder(p->left);
    postorder(p->right);
    visit(p);
  }
}

template <class T>
void BST<T>::snapShot(ostream& out,BSTNode<T> *p)
{
 out << '\"' << p->key << '\"';
 if(p->left != 0 || p->right != 0) {
  out << '[';
  if(p->left==0)
   out << "\"\"";
  else
   snapShot(out,p->left);
  out << ',';
  if(p->right==0)
   out << "\"\"";
  else
   snapShot(out,p->right);
  out << ']';
 }
}

template<class T>
void BST<T>::deleteByCopying(BSTNode<T>*& node) {  
  BSTNode<T> *previous, *tmp = node;
   if (node->right == 0)         // node has no right child;
     node = node->left;  
   else if (node->left == 0)       // node has no left child;
     node = node->right;
   else {
     tmp = node->left;         // node has both children;
     previous = node;         // 1.
     while (tmp->right != 0) {     // 2.
       previous = tmp;
       tmp = tmp->right;
     }
     node->key = tmp->key;       // 3.
     if (previous == node)
        previous->left = tmp->left;
     else previous->right = tmp->left; // 4.
   }
   delete tmp;              // 5.
}

// findAndDeleteByCopying() searches the tree to locate the node containing
// el. If the node is located, the function DeleteByCopying() is called.

template<class T>
void BST<T>::findAndDeleteByCopying(const T& el) {  
  BSTNode<T> *p = root, *prev = 0;
   while (p != 0 && !(p->key == el)) {
     prev = p;
     if (p->key < el)
       p = p->right;
     else p = p->left;
   }
   if (p != 0 && p->key == el)
     if (p == root)
        deleteByCopying(root);
     else if (prev->left == p)
        deleteByCopying(prev->left);
     else deleteByCopying(prev->right);
   else if (root != 0)
     cout << "key " << el << " is not in the tree\n";
   else cout << "the tree is empty\n";
}

template<class T>
void BST<T>::deleteByMerging(BSTNode<T>*& node) {  
  BSTNode<T> *tmp = node;
  if (node != 0) {
    if (!node->right)      // node has no right child: its left
       node = node->left;   // child (if any) is attached to its parent;
    else if (node->left == 0)  // node has no left child: its right
       node = node->right;  // child is attached to its parent;
    else {           // be ready for merging subtrees;
       tmp = node->left;   // 1. move left
       while (tmp->right != 0)// 2. and then right as far as possible;
        tmp = tmp->right;
       tmp->right =      // 3. establish the link between the
        node->right;    //  the rightmost node of the left
                  //  subtree and the right subtree;
       tmp = node;      // 4.
       node = node->left;   // 5.
    }
    delete tmp;         // 6.
   }
}

template<class T>
void BST<T>::findAndDeleteByMerging(const T& el) {  
  BSTNode<T> *node = root, *prev = 0;
  while (node != 0) {
    if (node->key == el)
       break;
    prev = node;
    if (node->key < el)
       node = node->right;
    else node = node->left;
  }
  if (node != 0 && node->key == el)
     if (node == root)
       deleteByMerging(root);
     else if (prev->left == node)
       deleteByMerging(prev->left);
     else deleteByMerging(prev->right);
  else if (root != 0)
     cout << "key " << el << " is not in the tree\n";
  else cout << "the tree is empty\n";
}

#endif