hrishikesh10 hrishikesh10 - 4 years ago 73
C Question

Binary search tree delete not working, why?

I am trying to implement Binary search tree in C.
But I am stuck at the delete operation, when I run the code it doesn't delete the value specified.

Before calling delete:(calling

inorder()
)

16 19 23


After calling delete:(calling
inorder()
)

16 19 23


code:

void deleteNode(struct node *n, int data)
{
struct node *temp;
if(n->data==data)
{
if(n->left == NULL && n->right == NULL)
{
n=NULL;
}
else if(n->left == NULL && n->right!=NULL)
{
n->data = (n->right)->data;
n->right = NULL;
}
else if(n->left!=NULL && n->right == NULL)
{
n->data = (n->left)->data;
n->left=NULL;
}
else if(n->left != NULL && n->right != NULL)
{
temp = findMax(root);
n->data = temp->data;
temp = NULL;
}
}
else if(n->data > data)
{
deleteNode(n->left, data);
}
else if(n->data < data)
{
deleteNode(n->right, data);
}
}


I have other code which is working, but I want to know what is wrong with this code?

Edit:
I have edited the code with a few changes in it.

Now, When I try to delete the ROOT node.
I end up with this:
(inorder traversal)->
16 23 23


Now,
Why is this happening when
temp = NULL
is making the maximum node NULL.

Note: I am not initializing temp as the code has been changed and it is initialized just before its use (
temp = findMax(root)
).

code inorder():

void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\n", root->data);
inorder(root->right);
}
}

Answer Source

Use this alternative code or use your temp tree in your method

struct node *temp = n; //then use temp tree in code

Alternative method

struct node *delete(struct node *tree, int data)
{
    if(find(tree,data)==-1 || tree == NULL)
            return tree;

    if(tree->data == data)
        {   
            if(tree->left==NULL && tree->right==NULL)
               return NULL; 

            if(tree->right != NULL){
                tree->data = min(tree->right); 
                tree->right = delete(tree->right,min(tree->right)); 
                return tree;
            }

                tree->data = madata(tree->left); 
                tree->left = delete(tree->left,madata(tree->left)); 
                return tree;

        }

    if(tree->data < data)
    {
        tree->right= delete(tree->right,data);
        return tree;

    }

    tree->left= delete(tree->left,data);
    return tree;
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download