#include <iostream>

using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
};

bool find(TreeNode* root, int val)
{
  if (root == NULL) return false;
  if (root->val == val) return true;
  
  if (val < root->val) 
    return find(root->left, val);
  else
    return find(root->right, val);
  
}

TreeNode* insert(TreeNode* root, int val)
{
  if (root == NULL) 
    {
      TreeNode* newNode = new TreeNode;
      newNode->val = val;
      return newNode;
    }

  if (val < root->val) 
    root->left = insert(root->left, val);
  else
    root->right = insert(root->right, val);

  return root;  
}

int findMinVal(TreeNode* root)
{
  // Should throw an exception when root == NULL
  if (root->left == NULL) return root->val;

  return findMinVal(root->left);
}

int findMaxVal(TreeNode* root)
{
  // Should throw an exception here too when root == NULL
  if (root->right == NULL) return root->val;
  
  return findMaxVal(root->right);
}

TreeNode* remove(TreeNode* root, int val)
{
  if (root == NULL) return root;
  if (root->val == val)
    {
      // 0 children case:
      if (root->left == NULL && root->right == NULL)
	{
	  delete root;
	  return NULL;
	}
      
      // Right child only case
      else if (root->left == NULL && root->right != NULL)
	{
	  TreeNode* temp = root->right;
	  delete root;
	  return temp;
	}
      
      // Left child only case
      else if (root->left != NULL && root->right == NULL)
	{
	  TreeNode* temp = root->left;
	  delete root;
	  return temp;
	}

      // The hard case
      // if (root->left != NULL && root->right != NULL)
      else 
	{
	  // Find the minimum value of the large subtree, promote that 
	  // value to our spot, remove that value
	  int minVal = findMinVal(root->right);
	  root->val = minVal;
	  root->right = remove(root->right, val);	  
	  return root;
	}
    }
  
  if (val < root->val)
    root->left = remove(root->left, val);
  else
    root->right = remove(root->right, val);

  return root;
}

int main()
{
  TreeNode* root = NULL;

  // Insert some fairly random numbers
  root = insert(root, 10);
  root = insert(root, 11);
  root = insert(root, 4);
  root = insert(root, 14);
  root = insert(root, 15);
  root = insert(root, 18);
  root = insert(root, 1);
  root = insert(root, 3);
  root = insert(root, 12);
  root = insert(root, 8);

  cout << "The minimum value of the tree is " << findMinVal(root) << endl;
  cout << "The maximum value of the tree is " << findMaxVal(root) << endl;

  for (int i = 0; i < 20; ++i)
    {
      cout << "The value " << i << " is ";
      if (find(root, i))
	cout << "in ";
      else
	cout << "not in ";
      cout << "the tree." << endl;
    }

  
  
}