/*
 * Selected operations on a binary search tree.
 *
 * Copyright (c) 2001, 2003, 2013 - Russell C. Bjork
 */
 
#include <string>
using namespace std;

class Node
{
    public:
    
        Node(string key)
        : _key(key), _lchild(NULL), _rchild(NULL)
        { }
                
        string _key;
        Node * _lchild, * _rchild;
};

// Lookup node containing a key in a subtree with given root
// Return pointer to node, or NULL if not found.   Recursive version 

Node * lookupR(string key, Node * root)
{
    if (root == NULL)
    
        // Base case - key is not in the tree
        return NULL;
        
    else if (key == root -> _key)
    
        // Base case - we found the key
        return root;
        
    else if (key < root -> _key)
    
        // Recursive case - look in left subtree
        return lookupR(key, root -> _lchild);
        
    else
        // Recursive case - look in right subtree
        return lookupR(key, root -> _rchild);
}

// Same as above - non recursive version

Node * lookupNR(string key, Node * root)
{
    bool found = false;
    Node * t = root;
    
    while (! found && t != NULL)
    {
        if (key == t -> _key)
            found = true;
        else if (key < t -> _key)
            t = t -> _lchild;
        else
            t = t -> _rchild;
    }
    
    // Either we found it or we reached a NULL - so either
    // way t is correct
    
    return t;
}

// Insert new node containing a key in a subtree with given root
// Recursive version.  Note that pointer to root is passed by reference.

void insertR(string key, Node * & root)
{
    if (root == NULL)
    
        // Base case - insert the new node here
        root = new Node(key);
        
    else if (key < root -> _key)
    
        // Recursive case - insert into left subtree
        insertR(key, root -> _lchild);
        
    else
        // Recursive case - insert into right subtree
        insertR(key, root -> _rchild);
} 

// Same as above - non recursive version

void insertNR(string key, Node * & root)
{
    if (root == NULL)
    
        // Special case - totally empty tree
        root = new Node(key);
        
    else
    {
        // Work down to a node without a child on the
        // appropriate side, then insert new node there
                
        bool inserted = false;
        Node * t = root;
                
        while (! inserted)
        {
            if (key < t -> _key)
                if (t -> _lchild == NULL)
                {
                    t -> _lchild = new Node(key);
                    inserted = true;
                }
                else
                    t = t -> _lchild;
            else
                if (t -> _rchild == NULL)
                {
                    t -> _rchild = new Node(key);
                    inserted = true;
                }
                else
                    t = t -> _rchild;
        }
    }
}

// Remove the node containing a key in a subtree with given root.
// Return true if successful.  Note that pointer to root is passed by
// reference.  Recursive version only.  (Non-recursive is possible, but
// messy!)

bool remove(string key, Node * & root)
{
    if (root == NULL)
        
        // Base case - key is not in the tree
        return false;
                
    else if (key == root -> _key)
    {
        // We found the correct node
            
        if (root -> _lchild == NULL && root -> _rchild == NULL)
        {
            // Base case - it has no children - just delete it
                
            delete root;
            root = NULL;        // Set pointer in parent to NULL
            return true;
        }
            
        else if (root -> _lchild == NULL)
        {
            // Base case - it has only one child - on right - promote 
            // child's key to take its place, then delete child
                
            Node * d = root;
            root = root -> _rchild;     // Child replaces parent
            delete d;
            return true;
        }
                 
        else if (root -> _rchild == NULL)
        {
            // Base case - it has only one child - on left - promote 
            // child's key to take its place, then delete child
                
            Node * d = root;
            root = root -> _lchild;     // Child replaces parent
            delete d;
            return true;
        }

        else
        {
            // It has two children.  We will copy information up from
            // its inorder predecessor, then delete that node instead,
            // recursively.
                        
            Node * p = root -> _lchild;
            while (p -> _rchild != NULL)
                p = p -> _rchild;
            root -> _key = p -> _key;
            return remove(root -> _key, root -> _lchild);
        }
    }
                                        
    else if (key < root -> _key)

        // Recursive case - remove from left subtree
        return remove(key, root -> _lchild);
        
    else

        // Recursive case - remove from right subtree
        return remove(key, root -> _rchild);
}