#include <iostream>
#include <string>

using namespace std;

template <typename K, typename V> class BSTree {
public:
  BSTree() : root(nullptr) {}
  int height() const { return calcHeight(root); }
  void print() const {
    printPreorder(root);
    cout << "\nh = " << height() << endl;
  }
  void insertNode(const K &k, const V &v) { root = doInsertNode(root, k, v); }
  void deleteNode(const K &k) { root = doDeleteNode(root, k); }
  V &search(const K &k) const {
    bst_node *s = doSearch(root, k);
    if (s == nullptr) throw "Not found";
    return s->value;
  }

private:
  struct bst_node {
    K key;
    V value;
    bst_node *left, *right;
    bst_node(const K &k, const V &v)
        : key(k), value(v), left(nullptr), right(nullptr) {}
  };

  bst_node *root;

  static int calcHeight(bst_node *r) {
    if (r == nullptr) return -1;
    return 1 + max(calcHeight(r->left), calcHeight(r->right));
  }

  static bst_node *doSearch(bst_node *r, const K &k) {
    if (r == nullptr)
      return nullptr;
    if (r->key == k)
      return r;
    if (k < r->key)
      return doSearch(r->left, k);
    else
      return doSearch(r->right, k);
  }

  static bst_node *doInsertNode(bst_node *n, const K &k, const V &v) {
    if (n == nullptr)
      return new bst_node(k, v);
    if (n->key == k)
      n->value = v; // update if it exists
    else if (k < n->key)
      n->left = doInsertNode(n->left, k, v);
    else
      n->right = doInsertNode(n->right, k, v);
    return n;
  }

  static bst_node *doDeleteNode(bst_node *n, const K &key) {
    if (n == nullptr)
      return n;

    if (key < n->key)
      n->left = doDeleteNode(n->left, key);
    else if (key > n->key)
      n->right = doDeleteNode(n->right, key);
    else {
      // this is the node to delete
      bst_node *temp = n;
      if (n->left == nullptr && n->right == nullptr) {
        n = nullptr; // it's a leaf, just delete it!
        delete temp;
      } else if (n->left == nullptr) {
        n = n->right; // it has one right child, replace it with that!
        delete temp;
      } else if (n->right == nullptr) {
        n = n->left; // it has one left child, replace it with that!
        delete temp;
      } else {
        // the node has two children, find its inorder successor
        temp = minValueNode(n->right);
        // copy the inorder successor's content to this node
        n->key = temp->key;
        // delete the inorder successor
        n->right = doDeleteNode(n->right, temp->key);
      }
    }
    return n;
  }

  static bst_node *minValueNode(bst_node *n) {
    while (n->left != nullptr)
      n = n->left;
    return n;
  }

  static void printPreorder(bst_node *node) {
    if (node == nullptr) return;
    cout << node->key << ":" << node->value << " ";
    printPreorder(node->left);
    printPreorder(node->right);
  }
};

void demoPopulate(BSTree<int, string> &t) {
  t.insertNode(5, "five");
  t.insertNode(2, "two");
  t.insertNode(3, "three");
  t.insertNode(7, "seven");
  t.insertNode(4, "four");
  t.insertNode(10, "ten");
  t.insertNode(9, "nine");
  t.insertNode(11, "eleven");
}

void demoSearch() {
  BSTree<int, string> t;
  demoPopulate(t);
  t.print();
  try {
    cout << "Searching 1... " << t.search(1) << " found!" << endl;
  } catch (const char *exc) {
    cout << "\n  Exception searching 1: " << exc << endl;
  }
  try {
    cout << "Searching 9... " << t.search(9) << " found!" << endl;
  } catch (const char *exc) {
    cout << "\n  Exception searching 9: " << exc << endl;
  }
  cout << endl;
}

void demoDelete() {
  BSTree<int, string> t;
  demoPopulate(t);
  t.print();

  cout << "After deleting " << 3 << ":" << endl;
  t.deleteNode(3);
  t.print();
  cout << endl;

  cout << "After deleting " << 5 << ":" << endl;
  t.deleteNode(5);
  t.print();
  cout << endl;

  cout << "After deleting " << 7 << ":" << endl;
  t.deleteNode(7);
  t.print();
  cout << endl;
}

int main() {
  demoSearch();
  demoDelete();
}