/******      bst.h                  ******/
/* Contains ADT definition for binary search tree */
/* The datastructure of the binary search tree    */
/* and the operations provided on them is are     */
/* defined below.                                 */

#include <stdlib.h>
#include <stdio.h>


typedef struct STnode* BST;        /* BST is a pointer to a node of the tree */

struct STnode {
        int nData;   /* the data value stored in the tree */
        BST Left;    /* pointer to left child   */
        BST Right;   /* pointer to right child  */
        int size;    /* size of subtree rooted at this node */
	};

/* functions defined on BST   */
BST   STinit();   /* returns an initialized  BST */
int STempty (BST T);  /* returns true if BST is empty */
int STinsert (BST T, int nNewData); /* insert operation */
void STshow(BST T); /* display BST */
int STwhatToDel(BST T,int *small,int *big,int newDel); /* returns the 
           value(s) in BST which are closest to newDel */
int STrotateUpMax(BST T); /* internal function */ 
int STdelete(BST T, int key); /* Delete a key from the BST */