// binary_search_tree_p3_template.cpp:

#include <iostream>
#include <ctime>
#include <list>

template <typename T>
class binary_search_tree_p3_template
{
public:
	// this is the default constructor, it will populate the binary search tree every time an object is created, this is done 
	//	for testing purposes.
	// [x]
	binary_search_tree_p3_template();

	// this is the destructor, it will disallocate all of the nodes inside of the tree when the object is finally destroyed.
	// [x]
	~binary_search_tree_p3_template();

	// this method will return the maximum depth of the tree for the user to see.
	// [x]
	int calc_depth();

	// this method will return the total number of nodes inside of the tree. The difference here is that this method will 
	//	traverse the tree, it will simply return a value inside of the class, essentially, it's a getter.
	// [x]
	int get_num_nodes();

	// this method will return the total number of nodes inside of the tree. This method will have another function traverse the 
	//	binary search tree in order to calculate the total number of nodes inside of the tree.
	// [x]
	int calc_num_nodes();

	// this method will begin the process of having the entire tree re-balanced.
	// [x]
	void rebalance_tree();

	// this method will insert a node into the tree and will instantiate the root_node as well.
	// [x]
	void insert_node(T );

	// this method will print out the nodes inorder. This method will be as an extra layer of abstraction between the recursive 
	//	method of print_inorder_rec and the non-recursive print_tree method.
	// [x]
	void print_inorder();

	// this method will print out the nodes postorder. This method will be as an extra layer of abstraction between the recursive 
	//	method of print_postorder_rec and the non-recursive print_tree method.
	// [x]
	void print_postorder();

	// this method will act as extra abstraction between the recursive deletion algorithm and method that asks the user for a 
	//	node to delete.
	// [x]
	void delete_node(T );

private:
	// the structure that will simulate a node inside of a binary search tree.
	struct node
	{
		// the default value that will be stored inside of the tree node.
		T value;

		// the pointer that will point to the right subtree of the current node.
		struct node * right;
		// the pointer that will point to the left subtree of the current node.
		struct node * left;
		// the pointer that will point to the parent node of the current node.
		struct node * up;
	};

	// this pointer will point to the root of the tree.
	node * root_node;
	// this pointer will be used during the reconstruction of the tree when we are trying to balance it. This will be used to 
	//	store a pointer of a node above the current one.
	node * above_node;

	// this value will hold the total number of nodes inside of the tree.
	int total_nodes;

	// -----------------------------------------------------
	// These methods are here for insertion of nodes into the tree.
	// -----------------------------------------------------
	// this method will insert a node into the tree recursively.
	// [x]
	void insert_node_rec(node * , T );

	// -----------------------------------------------------
	// These methods are here for printing out the contens of the tree.
	// -----------------------------------------------------
	// this method will print out the nodes inorder. It will go through the tree recursively and print out its contents.
	// [x]
	void print_inorder_rec(node * );
	// this method will print out the nodes postorder. It will go through the tree recursively and print out hte its contents.
	// [x]
	void print_postorder_rec(node * );

	// -----------------------------------------------------
	// These methods will be used to destroy the tree when the object is destroyed.
	// -----------------------------------------------------
	// this method will begin to destroy the tree.
	// [x]
	void destroy_tree();
	// this method will recursively disallocate all of the nodes inside of the tree.
	// [x]
	void destroy_tree_rec(node * );

	// -----------------------------------------------------
	// These methods will be used to delete a specific node in the tree.
	// -----------------------------------------------------
	// this method will go through the tree and find the specified node that it wants to delete.
	// [x]
	void delete_node_rec(node ** , T );
	// this method will find the smallest node to the left of the node that we would like to delete. This method will be used 
	//	only when the node has 2 children below it.
	// [x]
	struct node * find_smallest(node ** );

	// -----------------------------------------------------
	// The below methods will compute the total number of nodes inside of the binary search tree, as well as its depth.
	// -----------------------------------------------------
	// the below method will compute recursively the total number of nodes inside of the binary search tree.
	// [x]
	void calc_num_nodes_rec(node * , int & );
	// the below method will compute recursively the maximum depth inside of the binary search tree.
	// [x]
	int calc_depth_rec(node * , int );

	// -----------------------------------------------------
	// The below methods will compute the total number of nodes inside of the binary search tree, as well as its depth.
	// -----------------------------------------------------
	// this method will take care of having the entire tree rebalanced. It will act as a layer of abstraction between the 
	//	non-recursive rebalance_tree method and a recursive one.
	// [x]
	void rebalance_tree_al(node ** );
	// this method will go through the entire tree recursively and then copy all of the values that are inside of the tree into 
	//	the linked list. Also, while doing the copying, the method will disallocate all of the nodes that are inside the tree. 
	//	In this instance the double pointer indirection will be used, so that the pointers that point to the individual nodes 
	//	can be set NULL, that way, in the future, there won't be any problems when attempting to traverse the tree.
	// [x]
	void ret_nodes_data(node ** , std::list<T> & );
	// this method will be responsible for rebuilding the entire tree.
	// [x]
	void rebuild_tree(node ** , std::list<T> & );
	// this method will copy a portion of a linked list to another linked list. The bool value will tell which portion of the 
	//	original list should be copied. If it's true, than that means that the left portion of the list will be copied into the 
	//	target list, otherwise the it's the right portion.
	// [x]
	void copy_list(std::list<T> & , std::list<T> & , bool );
};

template <typename T>
binary_search_tree_p3_template<T>::binary_search_tree_p3_template()
{
	// set the pointer that is pointing to the root node of the tree to NULL.
	root_node = NULL;
	// set the pointer that is pointing to the node that is above the current one to NULL.
	above_node = NULL;

	// set the total number of nodes to 0.
	total_nodes = 0;
}

template <typename T>
binary_search_tree_p3_template<T>::~binary_search_tree_p3_template()
{
	// destroy the tree once the object is being destroyed. This will prevent any further memory leaks.
	destroy_tree();
}

template <typename T>
void binary_search_tree_p3_template<T>::insert_node(T value)
{
	// increment the total number of nodes.
	total_nodes++;

	// check to make sure if the root_node is NULL. If it is, create a node and assign the first value to it.
	if(root_node == NULL)
	{
		// allocate the necessary memory for the new node.
		root_node = new node;

		// make some preliminary assignments.
		root_node -> value = value;
		root_node -> up = NULL;
		root_node -> right = NULL;
		root_node -> left = NULL;
	}
	else
	{
		insert_node_rec(root_node, value);
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::insert_node_rec(typename binary_search_tree_p3_template<T>::node * curr_node, T value)
{
	// check to see if the passed in value is greater than or less than the current node. If it is less than, attempt to insert 
	//	the node to the left of the current node.
	if((curr_node -> value) >= value)
	{
		// check to see if the left pointer is NULL. If it is NULL, simply insert the required value into the new position, 
		//	otherwise proceed to the left subtree of the current node.
		if((curr_node -> left) == NULL)
		{
			// create a new node, that will be inserted.
			node * new_node = new node;

			// make some preliminary assignments.
			new_node -> value = value;
			new_node -> up = curr_node;
			new_node -> left = NULL;
			new_node -> right = NULL;

			// have the left pointer of the current node point to the new_node, making the new node assigned to the current node.
			curr_node -> left = new_node;
		}
		else
		{
			// go to the left subtree of the current node.
			insert_node_rec((curr_node -> left), value);
		}
	}
	else
	{
		// check to see if the right pointer is NULL. If it is NULL, simply insert the required value into the new position, 
		//	otherwise proceed to the right subtree of the current node.
		if((curr_node -> right) == NULL)
		{
			// create a new node, that will be inserted.
			node * new_node = new node;

			// make some preliminary assignments.
			new_node -> value = value;
			new_node -> up = curr_node;
			new_node -> left = NULL;
			new_node -> right = NULL;

			// have the right pointer of the current node point to the new_node, making the new node assigned to the current node.
			curr_node -> right = new_node;
		}
		else
		{
			// go to the right subtree of the current node.
			insert_node_rec((curr_node -> right), value);
		}
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::print_inorder()
{
	// print out the contents of the node recursively.
	print_inorder_rec(root_node);
}

template <typename T>
void binary_search_tree_p3_template<T>::print_inorder_rec(typename binary_search_tree_p3_template<T>::node * curr_node)
{
	// check to see if this is a valid node. If it is, print out the contents of the node and keep going into it left and right 
	//	subtrees.
	if(curr_node != NULL)
	{
		// go to the supposed left sub-tree of the current node.
		print_inorder_rec(curr_node -> left);
		// print out the contents of the current node.
		std::cout << "|" << (curr_node -> value) << "| ";
		// go to the supposed right sub-tree of the current node.
		print_inorder_rec(curr_node -> right);
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::print_postorder()
{
	// print out the contents of the node recursively.
	print_postorder_rec(root_node);
}

template <typename T>
void binary_search_tree_p3_template<T>::print_postorder_rec(typename binary_search_tree_p3_template<T>::node * curr_node)
{
	// check to see if this is a valid node. If it is, print out the contents of the node and keep going into it left and right 
	//	subtrees.
	if(curr_node != NULL)
	{
		// print out the contents of the current node.
		std::cout << "|" << (curr_node -> value) << "| ";
		// go to the supposed left sub-tree of the current node.
		print_postorder_rec(curr_node -> left);
		// go to the supposed right sub-tree of the current node.
		print_postorder_rec(curr_node -> right);
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::destroy_tree()
{
	// disallocate the contents of the tree recursively.
	destroy_tree_rec(root_node);
}

template <typename T>
void binary_search_tree_p3_template<T>::destroy_tree_rec(typename binary_search_tree_p3_template<T>::node * curr_node)
{
	// check to see if the current node is not equal to NULL.
	if(curr_node != NULL)
	{
		// decrement the number of nodes inside of the tree by one.
		total_nodes--;
		// go all the way to the left of the current node.
		destroy_tree_rec(curr_node -> left);
		// print out the contents of the tree. This way, all of the values inside of the nodes will be outputted inorder.
		//std::cout << (curr_node -> value) << ", ";
		// go all the way to the right of the current node.
		destroy_tree_rec(curr_node -> right);

		// disallocate the contents of the existing node and set the pointer to NULL, so as to avoid any potential assignment 
		//	problems in the future.
		delete curr_node;
		curr_node = NULL;
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::delete_node(T value)
{
	// delete the desired node recursively.
	delete_node_rec( & root_node, value);
}

template <typename T>
void binary_search_tree_p3_template<T>::delete_node_rec(typename binary_search_tree_p3_template<T>::node ** curr_node, T del_value)
{
	// check to see if we found the desired value in the node.
	if((( * curr_node) -> value) == del_value)
	{
		// decrement the total number of nodes that are in the tree.
		total_nodes--;

		// check to see if the current node has no children below it.
		if(((( * curr_node) -> left) == NULL) && ((( * curr_node) -> right) == NULL))
		{
			// delete the node that you would like to.
			delete ( * curr_node);

			// set the pointer that is pointing to the current node to NULL, so that there won't be any assignment problems in 
			//	the future.
			( * curr_node) = NULL;
		}
		// check to see if there is a sub-tree to the left of the current node and no sub-tree to the right of the current node.
		else if(((( * curr_node) -> left) != NULL) && ((( * curr_node) -> right) == NULL))
		{
			// create a node that will store the address of the current node, which will be used for deletion.
			node * to_be_del = NULL;

			// get the address of the node that we would like to delete.
			to_be_del = ( * curr_node);

			// move the node that leads to the sub-tree to the left of the current node in place of the one that we would like 
			//	to delete.
			( * curr_node) = ( * curr_node) -> left;

			// delete the node that we would like to get rid of.
			delete to_be_del;

			// set the to_be_del node to NULL, so as to avoid any possible assignment problems in the future.
			to_be_del;
		}
		// check to see if there is a sub-tree to the right of the current node and no sub-tree to the left of the current node.
		else if(((( * curr_node) -> right) != NULL) && ((( * curr_node) -> left) == NULL))
		{
			// create a node that will store the address of the current node, which will be used for deletion.
			node * to_be_del = NULL;

			// get the address of the node that we would like to delete.
			to_be_del = ( * curr_node);

			// move the node that leads to the sub-tree to the left of the current node in place of the one that we would like 
			//	to delete.
			( * curr_node) = ( * curr_node) -> right;

			// delete the node that we would like to get rid of.
			delete to_be_del;

			// set the to_be_del node to NULL, so as to avoid any possible assignment problems in the future.
			to_be_del;
		}
		// if there are subtrees to the right and left of the current tree, you'll need to do some tricky programming in order 
		//	to delete that specific node :) .
		else
		{
			// create a pointer to a node that will point to the node that we would like to delete.
			node * to_be_del = NULL;
			// create a pointer to a node that will take place of the node that we would like to delete.
			node * rep_node = NULL;

			// get the address of a node that we would like to take place of the one that we would delete.
			rep_node = find_smallest( & (( * curr_node) -> right));

			// get the address of the node that we would like delete.
			to_be_del = ( * curr_node);

			// make some preliminary assignments to the values of the rep_node.
			rep_node -> up = NULL;
			rep_node -> left = NULL;
			rep_node -> right = NULL;
			rep_node -> up = ( * curr_node) -> up;
			rep_node -> left = ( * curr_node) -> left;
			rep_node -> right = ( * curr_node) -> right;

			// have the node that pointer that's pointing right now to ( * curr_node), start pointing to the node that should 
			//	replace it.
			( * curr_node) = rep_node;

			// delete the desired node and have its pointer set to NULL, so as to avoid any possible assignment problems in the 
			//	future.
			delete to_be_del;
			to_be_del = NULL;
		}
	}
	// see if the value of the current node is greater than the passed in value. If so, try to go to the left sub-tree of the 
	//	current node.
	else if((( * curr_node) -> value) > del_value)
	{
		// check to see if you can go to the left subtree of the current node.
		if((( * curr_node) -> left) != NULL)
		{
			delete_node_rec( & (( * curr_node) -> left), del_value);
		}
		// if you can't go to the left sub-tree of the current node, tell the user that the value that he's looking for does not 
		//	exist.
		else
		{
			std::cerr << "The value that you're looking for does not exist..." << std::endl << std::endl;
		}
	}
	else if((( * curr_node) -> value) < del_value)
	{
		// check to see if you can go to the left subtree of the current node.
		if((( * curr_node) -> right) != NULL)
		{
			delete_node_rec( & (( * curr_node) -> right), del_value);
		}
		// if you can't go to the left sub-tree of the current node, tell the user that the value that he's looking for does not 
		//	exist.
		else
		{
			std::cerr << "The value that you're looking for does not exist..." << std::endl << std::endl;
		}
	}
}

template <typename T>
typename binary_search_tree_p3_template<T>::node * binary_search_tree_p3_template<T>::find_smallest(
	typename binary_search_tree_p3_template<T>::node ** curr_node)
{
	// if you can go to the left, do so.
	if((( * curr_node) -> left) != NULL)
	{
		return find_smallest( & (( * curr_node) -> left));
	}
	// if there is only a sub-tree to the right of the current node, 
	else if((( * curr_node) -> right) != NULL)
	{
		// create a pointer to a node that will be able to hold the address of the node that we would like to return to the top.
		node * ret_node = NULL;

		// get the address of the node that we would like to return.
		ret_node = ( * curr_node);

		// get the pointer to the sub-tree to the right of the tree and move it in place of the current node. That way, the node 
		//	pointing to the current node will now point to the node that is the right sub-tree of the current node.
		( * curr_node) = ( * curr_node) -> right;

		// return the desired node to the top.
		return ret_node;
	}
	else
	{
		// create a pointer to a node that will be able to hold the address of the node that we would like to return to the top.
		node * ret_node = NULL;

		// get the address of the node that we would like to return.
		ret_node = ( * curr_node);

		// set the pointer pointing to the current node to NULL, so as to avoid any problems in the future during the traversal 
		//	of the tree.
		( * curr_node) = NULL;

		// return the desired node to the top.
		return ret_node;
	}
}

template <typename T>
int binary_search_tree_p3_template<T>::calc_num_nodes()
{
	// this value will contain the number of nodes inside of the binary search tree.
	int num_nodes = 0;

	// calculate the number of nodes inside of the binary search tree.
	calc_num_nodes_rec(root_node, num_nodes);

	// return the number of nodes inside the tree to the top.
	return num_nodes;
}

template <typename T>
void binary_search_tree_p3_template<T>::calc_num_nodes_rec(typename binary_search_tree_p3_template<T>::node * curr_node, int & total)
{
	// if this is a valid node, then simply increment the total counter and go to the potential right and left sub-trees of this 
	//	node.
	if(curr_node != NULL)
	{
		total++;
		calc_num_nodes_rec((curr_node -> left), total);
		calc_num_nodes_rec((curr_node -> right), total);
	}
}

template <typename T>
int binary_search_tree_p3_template<T>::get_num_nodes()
{
	// tell the user the number of nodes that are in the tree.
	return total_nodes;
}

template <typename T>
int binary_search_tree_p3_template<T>::calc_depth()
{
	// find the depth of the tree and return it to the user/top.
	return calc_depth_rec(root_node, 0);
}

template <typename T>
int binary_search_tree_p3_template<T>::calc_depth_rec(typename binary_search_tree_p3_template<T>::node * curr_node, int depth)
{
	// check to see if this is a valid node. If it's not a valid node, simply return a 0 as a value.
	if(curr_node != NULL)
	{
		// this integer will store the return value from the right sub-tree of the current node.
		int right_v = 0;
		// this integer will store the return value from the left sub-tree of the current node.
		int left_v = 0;

		// increment the current counter, so that it could be passed down the method.
		depth++;

		// pass in the values into the left and right sub-trees of the current node. Also, get the return values from those 
		//	methods.
		right_v = calc_depth_rec((curr_node -> left), depth);
		left_v = calc_depth_rec((curr_node -> right), depth);

		// compare the return values and have the largest one passed back to the top.
		if(right_v >= left_v)
		{
			return right_v;
		}
		else
		{
			return left_v;
		}
	}
	else
	{
		return depth;
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::rebalance_tree()
{
	rebalance_tree_al( & root_node);
}

template <typename T>
void binary_search_tree_p3_template<T>::rebalance_tree_al(typename binary_search_tree_p3_template<T>::node ** root)
{
	// create a node that will point to a completely new tree that will be created after the rebalancing is done.
	node * new_tree = NULL;

	// create a list that will store all of the values that are supposed to be inside of the old tree. This list will be around 
	//	for a limited number of time.
	list<int> temp_list;

	// create an iterator that will loop through the entire linked and print out its contents, so that the user may see for 
	//	testing purposes.
	list<int>::iterator iter;

	// copy the values that are inside of the current tree into the linked list and at the same time, destroy the values inside 
	//	of the old tree.
	ret_nodes_data(root, temp_list);

	// now try to rebuild the tree from scratch, given the linked list and the node new_tree.
	rebuild_tree( & new_tree, temp_list);

	// assign the new_node node to the root_node. That way, the original tree starts pointing to the new rebalanced tree and 
	//	other methods can continue on using root_node.
	( * root) = new_tree;
}

template <typename T>
void binary_search_tree_p3_template<T>::ret_nodes_data(typename binary_search_tree_p3_template<T>::node ** curr_node, std::list<T> & temp_list)
{
	// see first of all if the node is valid, if it is, the proceed with the copying of data and disallocation of the nodes.
	if(( * curr_node) != NULL)
	{
		// go all the way to the left sub-tree of the current node.
		ret_nodes_data( & (( * curr_node) -> left), temp_list);
		// insert the data that is in the node, at the end of the list. This is done in such a manner so that all of the values 
		//	inside of the list will be already sorted in an increasing order.
		temp_list.push_back(( * curr_node) -> value);
		// go all the way to the right sub-tree of the current node.
		ret_nodes_data( & (( * curr_node) -> right), temp_list);

		// disallocate the current node, then simply set it to NULL, so as to avoid any possible assignment problems in the 
		//	future.
		delete ( * curr_node);
		( * curr_node) = NULL;
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::rebuild_tree(typename binary_search_tree_p3_template<T>::node ** curr_node, std::list<T> & temp_list)
{
	// check to see if the list is larger than 2. If it is, that means that there are 3 or more values inside of the list, that 
	//	can be inserted into the new tree.
	if(temp_list.size() > 2)
	{
		// create a node that will be inserted in the tree.
		node * new_node = new node;

		// create 2 linked lists. These lists will hold the 2 halves of the temp_list. The only element that will not be in 
		//	the list is the middle value. The middle value will be found and 
		std::list<int> left_list;
		std::list<int> right_list;

		// copy the necessary data into the left_list.
		copy_list(left_list, temp_list, true);
		// copy the necessary data into the right_list.
		copy_list(right_list, temp_list, false);

		// do some preliminary assignments.
		new_node -> value = right_list.front();
		new_node -> left = NULL;
		new_node -> right = NULL;
		new_node -> up = above_node;

		// have the double indirection pointer point to the new_node, instead of NULL. This way, there won't be any problems 
		//	when attempting to traverse the tree later on.
		( * curr_node) = new_node;

		// delete the first node in the right list.
		right_list.pop_front();

		// set the above_node as the current one, so that a pointer in the recursion will recognize this as the true node 
		//	above it.
		above_node = ( * curr_node);
		// go down to the left of the current node.
		rebuild_tree( & (( * curr_node) -> left), left_list);
		// set the above_node as the current one, so that a pointer in the recursion will recognize this as the true node 
		//	above it.
		above_node = ( * curr_node);
		// go down to the right of the current node.
		rebuild_tree( & (( * curr_node) -> right), right_list);
	}
	// when the size is 2, that means that there are 2 more nodes that need to be inserted into the list in a specific manner, 
	//	so as not to cause any irregularities in the manner in which nodes are organized in a binary search tree.
	else if(temp_list.size() == 2)
	{
		// the below 2 nodes will be used to store the last 2 values inside of the list.
		node * new_node1 = new node;
		node * new_node2 = new node;

		// make some preliminary assignments to the first node, so that all of the values and pointers inside will function 
		//	correctly.
		new_node1 -> left = NULL;
		new_node1 -> right = new_node2;
		new_node1 -> up = above_node;
		new_node1 -> value = temp_list.front();
	
		// have the double indirection pointer now point to this node.
		( * curr_node) = new_node1;

		// make some preliminary assignments to the second node, so that all of the values and pointers inside will function 
		//	correctly.
		new_node2 -> left = NULL;
		new_node2 -> right = NULL;
		new_node2 -> up = new_node1;
		new_node2 -> value = temp_list.back();
	}
	// when the size is 1, that means that this is the last node in the list that can be inserted.
	else if(temp_list.size() == 1)
	{
		// create a node that will be inserted in the tree.
		node * new_node = new node;

		// make some preliminary assignments.
		new_node -> value = temp_list.front();
		new_node -> up = above_node;
		new_node -> left = NULL;
		new_node -> right = NULL;

		// have the node that is pointing from above to NULL, now point to the new_node.
		( * curr_node) = new_node;

		// pop off the last element that is inside the list.
		temp_list.pop_front();
	}
}

template <typename T>
void binary_search_tree_p3_template<T>::copy_list(std::list<T> & target, std::list<T> & source, bool copy_side)
{
    // if the copy_side is true, then that means that the ziel should contain the left part of the quelle linked list. 
	//	If it's false then it's the opposite.
    if(copy_side)
    {
		// create two iterators that will point to the beginning of the list.
		typename std::list<T>::iterator begin_iter = source.begin();
		typename std::list<T>::iterator end_iter = source.begin();

		// make 2 integers that will tell of the current position of the iterators, as well, as how many values one needs to 
		//	traverse in order to get to the cut-off point.
		//	This integer will point to the very beginning of the list, which will tell us which part of the source we need to 
		//		remove.
		int begin = 0;
		//	This integer will guide the end iterator to the point where the list should be spliced.
		int	end = (int)((source.size()) / 2);

		// move the iterators inside of the list to their specified positions.
		advance(begin_iter, begin);
		advance(end_iter, end);

		// splice the target list, so as to create a sub-set of the list.
		target.splice(target.begin(), source, begin_iter, end_iter);
    }
    else
    {
		// create two iterators that will point to the beginning of the list.
		typename std::list<T>::iterator begin_iter = source.begin();
		typename std::list<T>::iterator end_iter = source.begin();

		// make 2 integers that will tell of the current position of the iterators, as well, as how many values one needs to 
		//	traverse in order to get to the cut-off point.
		//	Add one so as to avoid the central value in the list.
		int begin = 0;
		//	Subtract one from the size, so as to get the to the very last value inside of the list.
		int end = (int)source.size();

		// move the integers inside of the list to their specified positions.
		advance(begin_iter, begin);
		advance(end_iter, end);

		// splice the target list, so as to create a sub-set of the list.
		target.splice(target.begin(), source, begin_iter, end_iter);
    }
}

using namespace std;

// this main method will be used for testing purposes.
int main()
{
	// create a tree.
	binary_search_tree_p3_template<int> b_tree;

	srand((unsigned)time(NULL));

	for(int i = 0; i < 20; i++)
	{
		b_tree.insert_node(((rand()) / 300));
	}

	b_tree.rebalance_tree();

	cout << "Post-order..." << endl;
	b_tree.print_postorder();
	cout << endl << endl << "In-order..." << endl;
	b_tree.print_inorder();
	cout << endl << endl;

	b_tree.insert_node(33);

	cout << "Post-order..." << endl;
	b_tree.print_postorder();
	cout << endl << endl << "In-order..." << endl;
	b_tree.print_inorder();
	cout << endl << endl;

	b_tree.delete_node(24);

	cout << "Post-order..." << endl;
	b_tree.print_postorder();
	cout << endl << endl << "In-order..." << endl;
	b_tree.print_inorder();
	cout << endl << endl;

	return 0;
}