#include <iostream>

using namespace std;


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

int treeMin(Node* tree)
{
  if (tree->left != NULL) return treeMin(tree->left);
  return tree->val; 
}

int treeMax(Node* tree)
{
  if (tree->right != NULL) return treeMax(tree->right);
  return tree->val;
}

Node* remove(Node* tree, int val)
{
  if (tree == NULL) return NULL;
  
  if (val < tree->val)
    {
      tree->left = remove(tree->left, val);
      return tree;
    } 
  else if (val > tree->val) 
    {
      tree->right = remove(tree->right, val);
      return tree;
    }
  
  if (tree->left == NULL && tree->right == NULL)
    {
      // We are a leaf, simple case
      delete tree;

      return NULL;
    } 
  else if ((tree->left == NULL) || (tree->right == NULL))
    {
      // We have one child, promote that one
      if (tree->left == NULL)
	{
	  // promote the right side
	  tree->val = tree->right->val;

	  delete tree->right;

	  tree->right = NULL;
	} else {
	  // promote the left side
	  tree->val = tree->left->val;

	  delete tree->left;

	  tree->left = NULL;
	}
    }
  else
    {
      // The tough case
      // Get the value of the minimum element of the right subtree
      tree->val = treeMin(tree->right);

      tree->right = remove(tree->right, tree->val);
    }

  return tree;
}

Node* insert(Node* tree, int val)
{
  if (tree == NULL)
    {
      Node* newNode = new Node();
      newNode->val = val;
      newNode->left = NULL;
      newNode->right = NULL;

      return newNode;
    }

  if (val < tree->val)
    {
      tree->left = insert(tree->left, val);
    } else {
      tree->right = insert(tree->right, val);
    }

  return tree;
}

void printTree(Node* tree, int depth)
{
  if (tree == NULL) return;

  for (int i = 0; i < depth; i++)
    cout << " ";
  cout << tree->val << endl;

  printTree(tree->left, depth + 1);
  printTree(tree->right, depth + 1);
}

void preOrder(Node* tree)
{
  if (tree == NULL) return;
  cout << tree->val << " ";
  preOrder(tree->left);
  preOrder(tree->right);
}

void postOrder(Node* tree)
{
  if (tree == NULL) return;
  postOrder(tree->left);
  postOrder(tree->right);
  cout << tree->val << " ";

}

void inOrder(Node* tree)
{
  if (tree == NULL) return;
  inOrder(tree->left);
  cout << tree->val << " ";
  inOrder(tree->right);
}

bool isEmpty(Node* tree)
{
  return (tree == NULL);
}

unsigned int size(Node* tree)
{
  if (tree == NULL) return 0;

  return 1 + size(tree->left) + size(tree->right);
}

#define MAX(a, b) ((a) > (b) ? (a) : (b))

unsigned int depth(Node* tree)
{
  if (tree == NULL) return 0;
  
  return 1 + MAX(depth(tree->left), depth(tree->right)); 
}

bool search(Node* tree, int val)
{
  if(tree == NULL) return false;
  if(tree->val == val)
    {
      return true;
    }
  if(tree->val < val)
    {
      return search(tree->left, val);
    }
  else // (tree->val > val)
    {
      return search(tree->right, val);
    }
}

void deleteTree(Node* tree)
{
  if (tree == NULL) return;
  
  deleteTree(tree->left);
  deleteTree(tree->right);
  
  delete tree;

}

int main()
{
  Node* tree = NULL;

  tree = insert(tree, 5);
  tree = insert(tree, 3);
  tree = insert(tree, 10);
  tree = insert(tree, 4);
  
  tree = remove(tree, 4);

  printTree(tree, 0);
   
  cout << endl;
  
  cout << "pre" << endl;
  preOrder(tree);
  cout << endl;

  cout << "in" << endl;
  inOrder(tree);
  cout << endl;

  cout << "post" << endl;
  postOrder(tree);
  cout << endl;

  cout << "Number of nodes: " << size(tree) << endl;
  cout << "Depth of tree " << depth(tree) << endl;

}