#ifndef _TREE_H_
#define _TREE_H_

// the only fields you should use from the TreeNode struct in your program
// are the left and right pointers. You should use these pointers to traverse
// your tree. The height, is_sentinel, and parent fields are working fields
// used by the various tree algorithms. Not all the trees use these fields
// so you cannot count on them to be accurate. In particular you cannot use
// the height field to find the height of your tree.
typedef struct node {
    char *key;
    struct node *left;  
    struct node *right;
    int height;	  
    int is_sentinel; 
    struct node *parent; 
} TreeNode;

// routine for accessing the root of a tree
TreeNode *tree_root(TreeNode *sentinel_node);

// routine for finding a string in a splay tree--returns a node containing
// the string if the string is found and 0 otherwise
TreeNode *splay_tree_find(TreeNode *sentinel_node, char *key);

// routines for creating the trees you will use in this lab. Each of these
// routines creates a sentinel node for the tree. You will pass this sentinel
// node to the find and insert routines. If you want to obtain a pointer to
// the root node in order to compute the height or depth of the tree, you
// should call the tree_root function and pass it the tree's sentinel node
TreeNode *make_splay_tree();
TreeNode *make_avl_tree();
TreeNode *make_bstree();

// routines for inserting character strings into the trees you will use 
// in this lab
TreeNode *splay_tree_insert(TreeNode *sentinel_node, char *key);
TreeNode *avl_tree_insert(TreeNode *sentinel_node, char *key);
TreeNode *bstree_insert(TreeNode *sentinel_node, char *key);

#endif