Node Refusing to Delete in Binary Search Tree

Question

I'm currently writing a program that will delete a node from a binary search tree (among other things, but the deletion is my issue) and I'm having a problem with the final step of deletion, specifically the final step of deleting a node with 2 children.

The way that I'm deleting is the way described here. I take the farthest down left child-node (if on the right side of root) or the farthest down right child-node (if on the left) and replace the value of the node I want to delete with that value, then delete the node I just copied from.

I have all the steps complete except deleting the node I copied from; for some reason my code does not properly delete it and creates a random number value as well as a random parent value for the node I just tried to delete. I believe this is caused by an unrepaired link in the tree somewhere but being a non-experienced programmer, I cannot find it. Hopefully someone more well versed in BSTs can help me.

Here is my code (I only included code that influences the deletion function, I didn't think it necessary to include things that come after such as the destroy function):

#include <iostream>

using namespace std;

struct node
{
    int data; //Stores data within the trees pointers
    node * parent; //Used to move up in the tree
    node * left; //Used to move left in the tree
    node * right; //Used to move right in the tree
};

node * create (int data, node **tree); //Function to insert elements into the tree

void printTree (node * tree); //Function to print the tree

node *search(int key, node *tree); //Function to find data in the tree

node * delNode (node * tree, node * root); //Function to delete data from the tree

node * findSmallestRight (node * tree, node **smallest);

node * findLargestLeft (node * tree, node **smallest);

int main()
{
    node * root = NULL; //Root will be the first element in the tree
    node * current = NULL; //Return value for insert function to keep changes
    int value; //Value entered by user

    while (true) //Loop to fill tree with data
    {
        cout << "Enter an integer, 0 to quit" << endl;
        cin >> value;
        if (value == 0) //Quit when 0 is entered, BEFORE entering it into the tree
            break;
        current = create(value, &root); //Insert value into the tree
        cout << "After inserting " << value << " tree is:" << endl;
        printTree(root); //Print the tree
    }
    while (true) //Loop to delete data from tree
    {
        cout << "Search for a value to delete from the tree, 0 to quit" << endl;
        cin >> value;
        if (value == 0)
            break;
        current = search(value, root); //Find the value in the tree
        if (current == NULL)
            cout << value << " is not in tree. Could not delete." << endl;
        else
        {
            root = delNode(current, root); //Delete the data
            cout << value << " has been deleted. The tree is now:" << endl;
            printTree(root); //print the tree
        }
    }
    destroy(root); //Destroy the tree
    return 0;
}

void printNode (node * Node) //Function to print a node in the tree
{
    cout << "addr= " << Node << " parent= " << Node->parent << " left= " << Node->left << " right= " << Node->right << " data= " << Node->data << endl;
}

node * createNode (int data) //Function to create a new node in the tree
{
    node * newNode = NULL; //Create a new pointer
    newNode = new node; //Make that pointer a node
    newNode->data = data; //Fill it with data
    newNode->left = NULL; //Make it point left to NULL
    newNode->right = NULL; //and right to NULL
    return newNode;
}

node * create (int data, node **tree) //Function to insert elements into the tree
{
    node * newNode = NULL; //Create a new pointer
    if ((*tree) == NULL) //Check if tree exists already
    {
        //If it doesn't, create a new node and make it the root
        newNode = createNode(data);
        *tree = newNode;
        (*tree)->parent = NULL; //Root has a parent of NULL
    }
    else if (data < (*tree)->data) //If the data is smaller than root, insert on the left
    {
        if ((*tree)->left == NULL)//If there is no node on the left, create a new one and point to it
        {
            newNode = createNode(data);
            (*tree)->left = newNode;
            newNode->parent = *tree;
        }
        else
        {
            newNode = create(data, &((*tree)->left));//If there is a node on the left, repeat function until there isn't
        }
    }
    else //If the data is greater than or equal to root, insert on the right
    {
        if ((*tree)->right == NULL)
        {
            newNode = createNode (data); //If there is no node on the right, create a new one and point to it
            (*tree)->right = newNode;
            newNode->parent = *tree;
        }
        else
        {
            newNode = create(data, &((*tree)->right)); //If there is a node on the right, repeat function until there isn't
        }
    }
    return newNode; //Return the new node to keep the changes to the value
}

void printTree (node * tree) //Function to print the tree
{
    if (tree != NULL) //Check if tree actually existsreturn root;
    {
        //Recursively print the left side, then the root, then the right side
        printTree(tree->left);
        printNode(tree);
        printTree(tree->right);
    }
}

node *search(int key, node *tree) //Function to find data in the tree
{
    if (tree == NULL || tree -> data == key)
    {
        return tree; //If the data either does not exist or has been found, return
    }
    if (key < tree->data)
    {
        return search(key, tree->left); //If the data is less than the current data, keep checking the left
    }
    else
    {
        return search(key, tree->right); //If the data is more than the current data, keep checking the right
    }
}

node * delNode (node * tree, node * root)
{
    node * parent; //Node for quick-reference and manipulation of tree's parent
    if (tree->parent != NULL) //If tree value is not root assign a parent (root has parent of NULL so assigning would crash)
    {
        parent = tree->parent;
    }
    node * curr = tree;
    //Removing node with 2 children on right
    //There would also be cases for no children, 1 child, and 2 children on left but I did not include them as the two former are done and the latter can be copied once this is solved :)
    else if (tree->left != NULL && tree->right != NULL && parent->right == tree && parent != NULL)
    {
        node * smallest; //Node to find smallest data value on left side
        //Initialise and make it point to nothing
        smallest = new node;
        smallest->left = NULL;
        smallest->right = NULL;
        smallest->parent = NULL;

        node * nReplace = NULL; //Node to replace data in tree
        //Initialise and make it point to nothing
        nReplace = new node;
        nReplace->left = NULL;
        nReplace->right = NULL;
        nReplace->parent = NULL;

        nReplace = findSmallestRight(tree, &smallest); //Function to find smallest data value on right side
        tree->data = nReplace->data; //Replace tree's data with the new data
        cout << nReplace << " " << nReplace->data << endl; //Debugging code
        delete nReplace; //Delete nReplace
        cout << nReplace << " " << nReplace->data << endl; //Debugging code
    }
    return root; //Return root to keep changes in tree
}

node * findSmallestRight (node * tree, node **smallest) //Function to find smallest data value on right side
{
    node * parent = tree->parent; //Node for easy manipulation of tree's parent
    //Check if current value is a potential candidate for smallest
    if (tree->left == NULL && tree->right == NULL && parent->left == tree)
    {
        *smallest = tree; //If it is, make smallest equal to it
    }
    if (tree->left == NULL && tree->right != NULL) //Check if the are only branches on the right
    {
        findSmallestRight (tree->right, smallest); //Recurse through the right
    }
    else if (tree->left != NULL && tree->right == NULL) //Check if there are only branches on the left
    {
        findSmallestRight (tree->left, smallest); //Recurse through the left
    }
    else if (tree->left == NULL && tree->right == NULL) //Check if there are no branches on both sides
    {
        return *smallest; //Return the smallest
    }
    else
    {
        //If there are branches on both sides recurse through both
        findSmallestRight (tree->left, smallest);
        findSmallestRight (tree->right, smallest);
    }
    return *smallest; //Return the smallest
}

Answer 1

I think your findSmallestRight() is all messed up from recursion to returning the values.

You just have to find the SMALLEST element on the Right subtree i.e for the right child go on iterating it's Left children until last one, that'll be minimum one.

Code is as simple as : (First see picture for name associations)

if (current->left != NULL && current->right != NULL) //condition if you Current Node (to be deleted) has 2 Children
  {      if((current->right)->left!=NULL) //If Right Child has left child go till last leftmost child.
        {
            Node* leftCurrent;
            Node* leftCurrentPred;
            leftCurrentPred=current->right;
            leftCurrent=(current->right)->left;
            while(leftCurrent->left != NULL)
            {
                leftCurrentPred=leftCurrent;
                leftCurrent=leftCurrent->left;
            }
            current->data=leftCurrent->data;
            delNode(leftCurrent, root); //Delete leftCurrent node i.e node with no child
            leftCurrentPred->left=NULL;
            cout<<item<<" has been removed from the Tree."<<endl;
        }
        else
        {  //If Right Child of current doesn't has Left child it is itself smallest one.
            Node* temp=current->right;
            current->data=temp->data;
            current->right=temp->right;
            delNode(temp,root); //Delete temp node i.e node with no child
            cout<<item<<" has been removed from the Tree."<<endl;
        }
}