#include <iostream.h>
#include <stdlib.h>

class BinarySearchTreeNode
{

public:
    BinarySearchTreeNode(float d)
    {
        data = d;
        left = right = NULL;
    }

    float                   data;
    BinarySearchTreeNode *  left;
    BinarySearchTreeNode *  right;
} ;

void FindAndRemoveFromTree(float target);
void FindAndRemoveFromTreeNonRoot(BinarySearchTreeNode *pNode, float target);

BinarySearchTreeNode *pRoot;

void FindAndRemoveFromTree(float target)
{
    // We basically end up writing this function twice: once for the
    // special case of removing the root, and then again for the normal
    // case of removing something from inside the tree.  Better ways to do this:
    //
    // The Kruse book makes clever use of reference parameters to pass a pointer
    //      to a node by reference.  Really cool, but we haven't spent a lot of 
    //      time on references, and I don't want to just for this topic.
    //
    // I took that code & modified it to use a "pointer to pointer" instead of a
    // reference to a pointer.  Same idea as the Kruse book, but it took about an
    // hour of class time to explain and most people didn't seem to really get it.
    // 
    // So I'll write the code twice here, and if you've got better ideas about how
    // to go about doing this, please let me know :)
    
    if (pRoot == NULL)
        return;
    else if ( pRoot->data == target)
    {
        BinarySearchTreeNode *temp;
        // This first if statement actually handles two situations:
        // 1) The root has no children.
        //      root->left is NULL, and so is root->right
        //      This case will properly remove the root node, and set
        //      root to be NULL.
        // 2) The tree has only one child, and that child is a right
        //      child.
        //      This case will properly splice the root out by 
        //      replacing the root with it's single child
        if(pRoot->left == NULL)
        {
            // Remember the starting root
            temp = pRoot;
            // Remove that node from the tree
            pRoot = pRoot->right;
            // Delete the memory used by that node
            delete temp;
        }
        else if (pRoot->right == NULL)
        {
            // If we got to this point, it's because pRoot->left != NULL,
            // and pRoot->right does, so we know that the pRoot has one
            // child.
            temp = pRoot;
            // Remove that node from the tree
            pRoot = pRoot->left;
            // Delete the memory used by that node
            delete temp;
            // This code is almost identical to the prior one - there's
            // got to be an elegant way to factor this.  Any suggestions?
        }
        else
        {
            // This is the more tricky case - we need to overwrite
            // the root with it's sucessor (or predecesor)
            BinarySearchTreeNode *pred;
            BinarySearchTreeNode *parent;

            // Find the next smallest node, then
            // Replace the root with that one.
            // parent will point to the parent of that node.
            parent = pRoot;
            pred = pRoot->left;
            while(pred->right != NULL)
            {
                parent = pred;
                pred = pred->right;
            }
            
            // pred now points at the target node, and parent
            // now points at the node above it.

            // Copy over the data here
            pRoot->data = pred->data;

            // Then get rid of it, here.

            // If the left subtree doesn't have any right subtrees,
            // then we need to replace the target with the contents of the
            // left node.
			if (pRoot->left == pred)
			{
				temp = pred;
				pRoot->left = pred->left;
				delete temp;
			}
			else // parent->right == pred
			{
				temp = pred;
				parent->right = pred->left;
				delete temp;
			}
		}
	}
    else
        // At this point, we know the target value isn't at the root, and there's
        // at least one node in the tree.  Call this other version to handle
        // the 'normal' case:
        FindAndRemoveFromTreeNonRoot(pRoot, target);
}

void FindAndRemoveFromTreeNonRoot(BinarySearchTreeNode *node, float target)
{
    if (node == NULL)
        return;

    // In order to splice something out of the list, we need to keep 
    // track of it's parent.
    BinarySearchTreeNode *parent = node;

    while( node != NULL && node->data != target )
    {
        if (target < node->data)
        {
            parent = node;
            node = node->left;
        }
        else if(node->data < target )
        {
            parent = node;
            node = node->right;
        }
    }

	// WE didn't find the value in the tree
	if(node == NULL)
		return;

    // If we found it, do all this
    // node->data == target
    {
        if (node->left == NULL)
        {
            // Splice the node out of the list by replacing
            // it with it's right subtree (note: right subtree
            // may be NULL)
            BinarySearchTreeNode *temp = node;
            if (parent->left == node)
                parent->left = node->right;
            else
                parent->right = node->right;

            delete temp;
        }
        else if (node->right == NULL)
        {
            // If we got to this point, it's because node->left != NULL,
            // and node->right does, so we know that the tree has one
            // child.
            BinarySearchTreeNode *temp = node;
            // Remove that node from the tree
            if (parent->left == node)
                parent->left = node->left;
            else
                parent->right = node->left;

            // Delete the memory used by that node
            delete temp;
        }
        else
        {
            // This is the more tricky case - we need to overwrite
            // the node with it's predecesor
            BinarySearchTreeNode *pred;
            BinarySearchTreeNode *temp;

            // Find the next smallest node (the predecessor), then
            // Replace the node with that one.
            // parent will point to the parent of that node.
            parent = node;
            pred = node->left;
            while(pred->right != NULL)
            {
                parent = pred;
                pred = pred->right;
            }
    
            // pred now points at the target node, and parent
            // now points at the node above it.

            // Copy over the data here
            node->data = pred->data;

            // Now we've "deleted" the value stored at node
            // All that's left is to get rid of the predecessor
            // by splicing it out of the list.
            temp = pred;
            parent->left = pred->left;
            delete temp;
        }
    }    
}


const int numTests = 8;
// WARNING: 
// This test leaks memory like there's no tomorrow.....
void main()
{
    int i = 0;

	char *sz = "The debugger is SOOOO cool!";

    while( i <= numTests)
    {
        pRoot = new BinarySearchTreeNode(10);
        pRoot->left = new BinarySearchTreeNode(4);
        pRoot->left->left = new BinarySearchTreeNode(2);
        pRoot->left->left->left = new BinarySearchTreeNode(1);
        pRoot->left->right = new BinarySearchTreeNode(6);
        pRoot->left->right->right = new BinarySearchTreeNode(8);

        switch(i++)
        {
            // remove value that's not there.
            case 0:
                FindAndRemoveFromTree(40);
                break;

            // Remove a leaf
            case 1:
                FindAndRemoveFromTree(1);
                break;

            // Remove a leaf
            case 2:
                FindAndRemoveFromTree(8);
                break;

            // non empty right subtree
            case 3:
                FindAndRemoveFromTree(6);
                break;

            // non empty leftsubtree
            case 4:
                FindAndRemoveFromTree(2);
                break;
    
            // non empty subtrees
            case 5:
                FindAndRemoveFromTree(4);
                break;

            // remove the root
            case 6:
                FindAndRemoveFromTree(10);
                break;

            // non empty subtrees, use that loop
            case 7:
                pRoot->left->left->right = new BinarySearchTreeNode(3);
                FindAndRemoveFromTree(4);
                break;

                // non empty subtrees, pred w/ left subtree
            case 8:
                pRoot->left->left->right = new BinarySearchTreeNode(3);
                pRoot->left->left->right->left = new BinarySearchTreeNode(2.5);
                FindAndRemoveFromTree(4);
                break;
        }
    }
}