#include "tree.h"


/* 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)
{
	if (T == NULL) { // empty tree
		T = (Tree) malloc(sizeof(Node)); // allocate space for it
		T->left = NULL;
		T->right = NULL;
		T->parent = parent_T;
		T->element = number; // store number in the node
		return T;
	}

	if (T->element < number) // number to be inserted in right subtree 
		T->right = insert_tree(number, T->right, T);

	if (T->element > number) // number to be inserted in left subtree 
		T->left = insert_tree(number, T->left, T);
	
	return T; // do nothing if number already present in tree
}


/* 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)
{
	if (T == NULL) // not found
		return NULL;

	if (T->element == number) // found
		return T;

	if (T->element < number) // number may be in the right subtree
		return search_tree(number, T->right);

	if (T->element > number) // number may be in the left subtree
		return search_tree(number, T->left);
}

/* 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)
{
	Tree S;
	Tree U;

	S = search_tree(number, T); // serch for the number in the tree

	if (S == NULL) // number does not exist
		return T;

	if ((S->left == NULL) && (S->right == NULL)) { // leaf node
		if (S->parent == NULL) { // S is also root!
			free(S); // remove S
			return NULL; // tree is empty now
		}
		else if (S == (S->parent)->left) // S is the left child of its parent
			(S->parent)->left = NULL; // remove the pointer
		else // S is the right child of its parent
			(S->parent)->right = NULL; // remove the pointer

		free(S); // remove S
	}
	else if (S->left == NULL) { // S has a non-empty right subtree
		U = find_smallest(S->right); // find the smallest node in the right subtree
		S->element = U->element; // move number in U to S
		delete_tree(U->element, S->right); // remove U from the tree
	}
	else { // S has a non-empty left subtree
		U = find_largest(S->left); // find the largest node in the left subtree
		S->element = U->element; // move number in U to S
		delete_tree(U->element, S->left); // remove U from the tree
	}

	return T;
}


/* Prints the numbers in tree T in sorted order */
void print_tree(Tree T)
{
	if (T == NULL) // do nothing
		return;

	print_tree(T->left); // print all the numbers in the left subtree
	printf(" %d", T->element); // print the number in the node
	print_tree(T->right); // print all numbers in the right subtree
}


/* Finds the smallest number in the tree T. Returns a pointer to
 * the node.
 */
Tree find_smallest(Tree T)
{
	if (T == NULL) // nothing is there!
		return T; 
	
	// keep moving left as long as one can
	for (; T->left != NULL; T = T->left);

	return T;
}

/* Finds the largest number in the tree T. Returns a pointer to
 * the node.
 */
Tree find_largest(Tree T)
{
	if (T == NULL) // nothing is there!
		return T; 
	
	// keep moving right as long as one can
	for (; T->right != NULL; T = T->right);

	return T;
}