Node* osDelete(Node* root, int i)
{
	if (root == NULL) //key i not found
		return root;
	else
	{
		if (i < root->key)
		{
			root->left = osDelete(root->left, i);
			return root;
		}
		else
			if (i > root->key)
			{
				root->right = osDelete(root->right, i);
				return root;
			}
			else //key i found
			{
				if(root->left == NULL)
					if (root->right == NULL) //leaf
					{
						free(root);
						return NULL;
					}
					else //single child to the right
					{
						Node* aux = root->right;
						free(root);
						return aux;
					}
				else // we have child on left
					if (root->right == NULL) // single child to the left
					{
						Node* aux = root->left;
						free(root);
						return aux;
					}
					else // 2 children.
					{
						Node* predecessor = root->left;
						Node* parent = root;
						findPredecessor(&predecessor, &parent);
						//printf("predecessor is %d, parent is %d\n", predecessor->key, parent->key);
						root->key = predecessor->key;
						if (parent == root)
						{
							root->key = predecessor->key;
							root->left = predecessor->left;
							free(predecessor);
						}
						else
						{
							root->key = predecessor->key;
							parent->right = predecessor->left;
							free(predecessor);
						}
						return root;
					}
			}
	}
}