//
// Binary Search Tree Implementation
// Base class: Binary Tree Implementation
//

#ifndef __BSTREE
#define __BSTREE

#include "btree.h"

template <class T>
class BSTree : protected BTree<T> {

 public:
  // Constructors
  BSTree () : BTree<T> () { }
  BSTree (T& item) : BTree<T> (item) { }

  // Make visibile traversals methods and height 
  virtual void Inorder (void (*Visit) (T&, int)) const
    { return BTree<T>::Inorder (Visit); }
  virtual void Preorder (void (*Visit) (T&, int)) const
    { return BTree<T>::Preorder (Visit); }
  virtual void Postorder (void (*Visit) (T&, int)) const
    { return BTree<T>::Postorder (Visit); }

  // Return Tree Height
  virtual int Height () const 
    { return BTree<T>::Height (); }

  // New methods: Insert and delete 
  virtual bool Insert (T* item) { return Insert (Root, *item); }
  virtual bool Insert (T& item) { return Insert (Root, item); }
  virtual bool Delete (T* item) { return Delete (Root, *item); }
  virtual bool Delete (T& item) { return Delete (Root, item); }

  // Different Search 
  virtual bool Search (T* item) const { return Search ((T&)*item); }
  virtual bool Search (T& item) const 
    { __TreeNode<T>* P; return Search (Root, P, item); }

  // Find Max and Min 
  virtual T& FindMax () const;
  virtual T& FindMin () const;

   friend ostream& operator << (ostream& out, BSTree<T>& t)
    { out << (BTree<T>&)t; return out; }

 private:
  bool Insert (__TreeNode<T>*&, T&);
  bool Delete (__TreeNode<T>*&, T&);
  bool Search (__TreeNode<T>*, __TreeNode<T>*&, T&) const; 

};

template <class T>
bool BSTree<T>::Insert (__TreeNode<T>*& R, T& item)
{
  __TreeNode<T>* P;

  if (R == NULL)
    R = new __TreeNode<T> (item, NULL, NULL); 
  else
    {
      // Find position where to insert
      if (Search (R, P, item) == true)
	return false;
      // Replace
      if (P->key < item)
	P->right = new __TreeNode<T> (item, P->right, NULL);
      else
	P->left = new __TreeNode<T> (item, P->left, NULL);
    }
  return true;
}

template <class T>
bool BSTree<T>::Delete (__TreeNode<T>*& R, T& item)
{
  __TreeNode<T> *P = R, *S = NULL, *PS = NULL, *PP = NULL;

  // Find Node to delete and its parent
  while (P && (P->key != item))
    {
      PP = P; 
      P = P->key > item ?  P->left : P->right;
    }
  if (P == NULL)
    return false;

  // Find Node used for replacement
  if (P->right != NULL)
    {
      for (S = P->right; S->left; S = S->left) PS = S;
      if (PS != NULL) 
	PS->left = S->right;
      else
	P->right = S->right;
    }
  else if (P->left != NULL)
    {
      for (S = P->left; S->right; S = S->right) PS = S;
      if (PS != NULL) 
	PS->right = S->left;
      else
	P->left = S->left;
    }

  // Replace
  if (PP != NULL)
    if (PP->key > item) 
      PP->left = S; 
    else 
      PP->right = S;
  else
    R = S;
  if (S != NULL)
    {
      S->left = P->left != S ? P->left : NULL;  
      S->right = P->right != S ? P->right : NULL; 
    }
  item = P->key; delete P;
  return true;
}

template <class T>
T& BSTree<T>::FindMax () const
{
  __TreeNode<T> *P = Root, *PP = NULL;

  // G to right until no more nodes are available
  for (; P->right;)
    P = P->right;
  return P->key;
}

template <class T>
T& BSTree<T>::FindMin () const
{
  __TreeNode<T> *P = Root, *PP = NULL;

  // Go to left until no more nodes are available
  for (; P->left;)
    P = P->left;
  return P->key;
}

template <class T>
bool BSTree<T>::Search (__TreeNode<T>* R, __TreeNode<T>*& P, T& item) const
{
  while (R != NULL)
    {
      P = R;
      if (R->key > item)
	R = R->left;
      else if (R->key < item)
	R = R->right;
      else
	{
	  item = R->key;
	  return true;
	}
    }
  return false;
}

#endif // __BSTREE