Binary Search Tree - Delete

Question

I am trying to write a program that takes in strings and places them in a binary search tree in alphabetical order once these are inserted into the tree, a user prompts for one word to be deleted, thus deleting that node from the tree, and then output the tree without that node back in order.

Everything works for this up to the delete function, the delete function does work, but its very weird how it deletes. I think currently it deletes a full side of the tree, because when I delete the last word, it typically works. I will upload my delete function and if more is needed I can upload the rest of my code.

Thanks!

template<typename T> void Delete(TreeNode<T>*& root, const T& data)
{
    if (root == NULL)
        return;
        if(data < root->Value)
            return Delete(root->Left, data);
        else if (root->Value > data)
            return Delete(root->Right, data);
        else
        {
            TreeNode<T>* old_root = root;
            if (root->Left == NULL)
            {
                root = root->Right;
            }
            else if (root->Right == NULL)
            {
                root = root->Left;
            }
            else
            {
                replace_parent(old_root, old_root->Left);
            }
            delete old_root;



    }

};

template<typename T> void replace_parent(TreeNode<T>*& old_root, TreeNode<T>*& root)
{
    if (root->Right != NULL)
    {
        replace_parent(old_root, root->Right);
    }
    else
    {
        old_root->Value = root->Value;
        old_root = root;
        root = root->Left;
    }
};

Answer 1

Lacqui is correct in his points.

let me tell you you that while deleting a node you need to replace it with either the max node in left sub tree or the minimum node in the right sub tree. for example: if you see the below picture:

if you want to delete the node 90,you need to take care that you replace it with either 80 which is its max node in the left subtree or the 92 which the minimum node in the right sub tree. you can keep any one approach.

so the algo will be : considering the left sub tree:

->if you find the node to delete,navigate to the max value in its left sub tree.

->assign the node's left as 50 and node right to be 150

->make 75->next as null and delete 90

Answer 2

Your cases for either left or right being NULL are good. However, your logic for neither of them being NULL is, unfortunately, failing.

If I'm reading your code (and understanding the function replace_parent() correctly, then if neither tree is empty you are replacing the current root with Left.

Ask yourself - what is happening to the values that are in the Right subtree?

What you need to do in order to delete a node is as follows:

1. Enter one of the subtrees. It looks like you've chosen your Left subtree, so we'll go from there.
2. Follow the opposite line of branches. In this example, keep going down the Right subtrees from your original Left. Keep going until you find a right-leaf node (no Right subtrees; Left is OK)
3. Remember the value of your right-leaf in a tmp variable.
4. Transfer the right-leaf's Left (whether NULL or not) to the right-leaf's position.
5. Take the tmp value and put it into your original 'to-delete' node.