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

typedef struct tree {
	int element; // number
	struct tree *left; // pointer to left child
	struct tree *right; // pointer to right child
	struct tree *parent; // pointer to parent
} Node; // one node of the tree

typedef Node *Tree; // pointer to a tree


/* Inserts number in the tree T. T points to
 * the root of the tree. Returns a pointer to the root.
 */
Tree insert_tree(int number, Tree T, Tree parent_T);

/* Searches for occurance of number in tree T. Returns a pointer
 * to the node containing number, if it exists.
 * Returns NULL otherwise.
 */
Tree search_tree(int number, Tree T);

/* Deletes the node containing number in the tree T, if it exists.
 * Returns pointer to the root of the tree, as it may change.
 */
Tree delete_tree(int number, Tree T);

/* Prints the numbers in tree T in sorted order */
void print_tree(Tree T);

/* Finds the smallest number in the tree T. Returns a pointer to
 * the node.
 */
Tree find_smallest(Tree T);

/* Finds the largest number in the tree T. Returns a pointer to
 * the node.
 */
Tree find_largest(Tree T);