void BST::insertItem(BTNode *& treePtr, const TreeItemType& newItem)
throw (TreeException) {
    treePtr = head->leftChildPtr;
    if (isEmpty()) { // tree is empty, hang off the head
        head->leftChildPtr = new BTNode(true, false, head, newItem, head, false);
        head->leftTag = true;
        head->leftChildPtr->valid = true;
        if (DEBUG) {
            cout << "~~~Empty tree, creating head node:" << endl;
            cout << head->toStr() << endl;
            cout << "~~~Creating root item:" << endl;
            cout << head->left()->toStr() << endl;
        }

        /*Iterative implementation: not working*/
    } else  {
        while (true) {
            if (DEBUG) {
                cout << "head's value is " << head->item.getKey() << endl;
                cout << "treePtr key is " << treePtr->item.getKey() << endl;
            }
            // go left
            if (newItem.getKey() < treePtr->item.getKey()) {
                if (!(treePtr->leftTag)){ //nothing to the left, position found
                    treePtr->leftChildPtr = new BTNode (true,
                            treePtr->leftTag, treePtr->leftChildPtr,
                            newItem, treePtr, false);
                    treePtr->leftTag = true;
                    treePtr->leftChildPtr->valid = true;
                    if (DEBUG) {
                        cout << "~Creating new Left Node:" << endl;
                        cout << "~~~~~Parent Node: " << treePtr->toStr() << endl;
                        cout << "~~~~~Child  Node: " << treePtr->left()->toStr() << endl;
                    }
                    break;  //finished inserting, we're done here
                } else { //otherwise, keep looking left
                    treePtr = treePtr->leftChildPtr;
                    continue;
                }
            } else { //go right
                if (!(treePtr->rightTag)) { //nothing to the right, position found
                    treePtr->rightChildPtr = new BTNode(true,
                            false, treePtr,
                            newItem,
                            treePtr->rightChildPtr, treePtr->rightTag);
                    treePtr->rightTag = true;
                    treePtr->rightChildPtr->valid = true;
                    if (DEBUG) {
                        cout << "~Creating new Right Node:" << endl;
                        cout << "~~~~~Parent Node: " << treePtr->toStr() << endl;
                        cout << "~~~~~Child  Node: " << treePtr->right()->toStr() << endl;
                    }
                    break; //finished inserting, we're done here
                } else { // keep looking right
                    treePtr = treePtr->rightChildPtr;
                    continue;
                }
            }
        }
    }
}