delete element BST

Question

When I delete 25 from BT than it works perfectly. But when I want to delete another number like 17, it deletes 17 with some other number are deleted from BT.

#include<iostream>
using namespace std;

struct node
{

    int data;
    node *left;
    node *right;
};

node *root = NULL;

node* createnode(int data)
{

    node *t = new node();
    t->data = data;
    t->left = NULL;
    t->right = NULL;
    return t;

}

node* min(node*);

node* insert(node *root, int data)
{

    if (root == NULL)
    {


        root = createnode(data);
        return root;
    }

    else{

        node *t = root;
        if (data <= t->data)
            t->left = insert(t->left, data);
        else{
            t->right = insert(t->right, data);
        }
    }
}

node* print(node *root)
{

    if (root == NULL)
    {

        return root;
    }

    else{

        cout << root->data << " ";
        print(root->left);
        print(root->right);
    }

    return root;
}

node* deleten(node *root, int data)
{

    if (root == NULL)
        return root;
    else{
        if (data<root->data)
            root->left = deleten(root->left, data);
        if (data>root->data)
            root->right = deleten(root->right, data);
        else{
            if (root->left == NULL && root->right == NULL)
            {
                node *t = root;
                root = NULL;
                delete t;
            }
            else if (root->left == NULL)
            {
                node *t = root;
                root = root->right;
                delete t;
            }
            else if (root->right == NULL)
            {
                node *t = root;
                root = root->left;
                delete t;
            }
            else{
                node *t = min(root->right);
                root->data = t->data;
                root->right = deleten(root->right, t->data);
            }
        }
        return root;
    }
}

node* min(node *root)
{

    if (root == NULL)
        return root;
    else{
        if (root->left != NULL)
            min(root->left);
        else{
            return root;
        }
    }
}

int main()
{

    root = insert(root, 15);
    root = insert(root, 10);
    root = insert(root, 8);
    root = insert(root, 12);
    root = insert(root, 11);
    root = insert(root, 20);
    root = insert(root, 23);
    root = insert(root, 17);
    root = insert(root, 25);
    root = print(root);
    cout << endl;
    root = deleten(root, 17);
    root = print(root);
}

case 1:

before deletion : 15 10 8 12 11 20 17 23 25

after deletion : 15 10 8 12 11 23 25 // root=deleten(root,17);

expectation : 15 10 8 12 11 20 23 25

case 2:

before deletion : 15 10 8 12 11 20 17 23 25

after deletion : 15 10 8 12 11 20 17 23 // root=deleten(root,25);

expectation : 15 10 8 12 11 20 17 23

case 3:

before deletion : 15 10 8 12 11 20 17 23 25

after deletion : 17 12 11 23 25 // root= deleten(root,8);

expectation : 15 10 12 11 20 17 23 25

Answer 1

The error is here:

if (data<root->data)
    root->left = deleten(root->left, data);
if (data>root->data)
    root->right = deleten(root->right, data);
else{
    //...
 }

If data is less than root->data, it will delete the left side of the tree, and the node, since you are using if not else if to test for the right.

The answer is simple, change to an else if instead:

if (data<root->data)
    root->left = deleten(root->left, data);
else if (data>root->data)
    root->right = deleten(root->right, data);
else{
    //...
 }