/* File: bst.H      Copyright glh 8/15/94 */
#ifndef BSTH
#define BSTH
#include <iostream.h>
#include <assert.h>
#include "bintree.H"

template<class T>
class BST : private virtual BinaryTree<T> {
  protected:
    Bnode<T>* SubtreeMin(Bnode<T>*) const;
    Bnode<T>* SubtreeMax(Bnode<T>*) const;
    Bnode<T>* Search(Bnode<T>*, int key, Boolean& success) const;
  public:
    BST() : BinaryTree<T>() {}
    BST(const T& elm) : BinaryTree<T>(elm) {}
    T& Search(int key, Boolean& success) const;
    Boolean Insert(T item);
    Boolean Delete(int key);
    T& Minimum(Boolean& success) const;
    T& Maximum(Boolean& success) const;
    T& Predecessor(int key, Boolean& success) const;
    T& Successor(int key, Boolean& success) const;
    BST<T>& operator=(const BST<T>&);
    friend ostream& operator<<(ostream& os, const BST<T>& tree)
    {return operator<<(os, (BinaryTree<T>)tree);}
};

#endif