//S-Tree header file
// This is the class interface for a list of integers


typedef int itemT;

class TNode {
public:
   itemT item;
   TNode *lchild, *rchild;
   // Constructor:
   TNode(itemT i, TNode * l, TNode * r) {
      item = i;
      lchild = l;
      rchild = r; 
   }
};
  
class S-Tree {

private: 

  TNode * root; // pointer to root of binary search tree
  void traverseAux( TNode* ); // Auxiliary functions
  int sizeAux( TNode* );
  int heightAux( TNode* );
  TNode * findAux(itemT, TNode *);
  void insertItemAux( itemT, TNode* &);
  void deleteItemAux( itemT, TNode* & );
  void insertItemIterativeAux( itemT, TNode* & );
public:

  S-Tree(); 
  // Constructor

  void traverse(void); 
  // Simply prints out the tree in order, one integer per line
  int size(void); 
  // Returns the size of the tree, i.e., number of members

  int height(void); 
  // Returns the height of the tree, i.e., the length of the longest
  // path from root to a leaf; height of empty tree is -1

  TNode * find( itemT );
  // Finds a given record in the tree, returns a ptr to record, or null if not found 

  void insertItem( itemT );
  // Inserts item into the ST, does nothing if item already in tree

  void deleteItem( itemT );
  // Deletes item from ST, does nothing if item is not in the tree

  void insertItemIterative( itemT );
  // Inserts item into the ST, does nothing if item already in tree

};