struct tree
	{
		int data;
		tree* left;
		tree* right;
	};
void build_Tree(int val, tree* pos)
	{
		if( val > pos->data)
			if (pos->right == NULL)
			{
				pos->right = new tree;
				pos->right->data = val;
				pos->right->left = NULL;
				pos->right->right = NULL;//create a new node from that link
			}
		
			else
				build_Tree(val, pos->right);

		if (val < pos->data)
			if (pos->left == NULL)
			{
				pos->left = new tree;
				pos->left->data = val;
				pos->left->left = NULL;
				pos->left->right = NULL;
			}
			else 
				build_Tree(val, pos->left);
		
}

void print_tree(tree* pos, int* arr, int size)
{
	int* arr_low;
	arr_low = new int [6];

	int* arr_high;
	arr_high = new int [6];
	
	for(int i = 0; i<3;i++)
	{
	if (pos->left != NULL)
	{
		print_tree(pos->left, arr, size);
		arr_low[i] = pos->data;
	}
	}
		
	for(int j = 3; j>0; j--)
	{
	if (pos->right != NULL)
	{
		print_tree(pos->right, arr, size);
		arr_high[j] = pos->data;
	}
	}
	arr = arr_low;
	arr = arr_high;
		
}
void binary_tree_sort(int* arr, int size)
{

	tree* root = new tree;
	root->data = arr[0];
	root->left = NULL;
	root->right = NULL;

	for(int i = 1 ; i<size ; i++)
	{
		build_Tree(arr[i], root);
	}
print_tree(root, arr, size);