// This implementation uses loops; see the text for an alternative
// that uses recursion.

template <class T>
class simple_bst_dictionary
{
  struct node 
  {
    T data;
    node * left;
    node * right;
    node(const T & x) : data(x), left(0), right(0) {}
  };

  node * root;

public:

  // Tree has a dummy node as root; real root is always the left
  // child of the dummy.

  simple_bst_dictionary() : root(new node(T())) {}

  // Exercise for the reader: copy constructor, destructor, assignment, etc.

  // Returns true if x is in the dictionary, false otherwise.
  bool lookup(const T & x)
  {
    node * p = root->left;
    while (p && p->data != x)
    {
      if (p->data < x)
        p = p->right;
      else 
        p = p->left;
    }
    return p;
  }

  void insert(const T & x)
  {
    node * p = root->left;
    node * parent = root;
    bool left_child = true;
    while (p && p->data != x)
    {
      parent = p;
      if (p->data < x)
      {
        left_child = false;
        p = p->right;
      }
      else 
      {
        left_child = true;
        p = p->left;
      }
    }

    if (p)
      return; // Nothing to do; x is already in dictionary.

    p = new node(x);
    if (left_child)
      parent->left = p;
    else
      parent->right = p;
  }

  void erase(const T & x)
  {
    node * p = root->left;
    node * parent = root;
    bool left_child = true;
    while (p && p->data != x)
    {
      parent = p;
      if (p->data < x)
      {
        left_child = false;
        p = p->right;
      }
      else 
      {
        left_child = true;
        p = p->left;
      }
    }

    if (!p)
      return; // Nothing to do; x is not in dictionary.

    if (!p->left)
    {
      // Node has zero or only one child (no left child).
      if (left_child)
        parent->left = p->right;
      else
        parent->right = p->right;
    }
    else if (!p->right)
    {
      // Node has only one child (has left but no right child).
      if (left_child)
        parent->left = p->left;
      else
        parent->right = p->left;
    }
    else
    {
      // Node has two children.
      // Find the in-order successor and its parent.
      node * s = p->right;
      node * s_parent = p;
      bool s_left_child = s->left;
      while (s && s->left)
      {
        s_parent = s;
        s = s->left;
      }

      // We could just swap the data values, but that might be 
      // expensive.  Instead we actually move the nodes around.

      // Remove the successor node from the tree.
      if (s_left_child)
        s_parent->left = s->right;
      else
        s_parent->right = s->right;

      // Replace node containing x with successor node.
      if (left_child)
        parent->left = s;
      else 
        parent->right = s;
      s->left = p->left;
      s->right = p->right;
    }
    delete p;
  }
};