#ifndef __BST_HEIGHT__
#define __BST_HEIGHT__ 1

typedef struct BTnode btnode;
typedef struct BSTree bstree;


struct BTnode {
    btnode *parent;
    btnode *left;
    btnode *right;
    int key;
};

struct BSTree {
    btnode *ROOT;
    int height;
};


void inorder_tree_walk(btnode *x);
btnode *tree_search(btnode *x, int key);
btnode *iterative_tree_search(btnode *x, int key);
btnode *tree_minimum(btnode *x);
btnode *tree_maximum(btnode *x);
btnode *tree_successor(btnode *x);
btnode *tree_predecessor(btnode *x);
void tree_insert(bstree *T, btnode *z);
void transplant(bstree *T, btnode *u, btnode *v);
void tree_delete(bstree *T, btnode *z);

btnode *make_btnode(int key);



#endif