#include <iostream>
#include <cstdlib>

struct notesTree
{
    int nProdID;
    notesTree* pLeftChild;
    notesTree* pRightChild;
    
    notesTree(int prod_id)
        : nProdID(prod_id)
        , pLeftChild()
        , pRightChild()
    {};
    
    notesTree(const notesTree& obj)
        : nProdID(obj.nProdID)
        , pLeftChild()
        , pRightChild()
    {};
};

void RemoveItem(notesTree** pp, int id)
{
    while (*pp)
    {
        if (id < (*pp)->nProdID)
            pp = &(*pp)->pLeftChild;
        else if ((*pp)->nProdID < id)
            pp = &(*pp)->pRightChild;
        else break;
    }
    
    if (*pp)
    {
        // save the victim pointer
        notesTree *victim = *pp;
        
        // move the left tree up a level
        *pp = victim->pLeftChild;
        
        // hang the victim's right child on the
        //  first null-right pointer in the left tree
        while (*pp)
            pp = &(*pp)->pRightChild;
        *pp = victim->pRightChild;
        
        delete victim;
    }
}

void InserItem(notesTree **pp, int id)
{
    while (*pp)
    {
        if (id < (*pp)->nProdID)
            pp = &(*pp)->pLeftChild;
        else if ((*pp)->nProdID < id)
            pp = &(*pp)->pRightChild;
        else break;
    }
    
    if (!*pp)
        *pp = new notesTree(id);
}

void InOrder(notesTree *p)
{
    if (!p)
        return;
    InOrder(p->pLeftChild);
    std::cout << p->nProdID << ' ';
    InOrder(p->pRightChild);
}


int main()
{
    notesTree *root = NULL;
    
    InserItem(&root, 5);
    InserItem(&root, 2);
    InserItem(&root, 1);
    InserItem(&root, 3);
    InserItem(&root, 4);
    InserItem(&root, 7);
    InserItem(&root, 6);
    InserItem(&root, 8);
    InserItem(&root, 9);
    
    InOrder(root);
    std::cout << std::endl;
    
    RemoveItem(&root, 5);
    InOrder(root);
    std::cout << std::endl;
    
    RemoveItem(&root, 6);
    InOrder(root);
    std::cout << std::endl;
    
    RemoveItem(&root, 1);
    InOrder(root);
    std::cout << std::endl;
    
    RemoveItem(&root, 8);
    InOrder(root);
    std::cout << std::endl;
    
    return EXIT_SUCCESS;
}