Member Avatar for abrarsyed

hello frends, i m havig a problem with the deletion of node int the tree plz help me to get my code debugged

void delete_node(struct node *temp,int data)
{
        struct node *temp2=NULL,*temp3;
       if(temp->data==data&&temp->left==NULL&&temp->right==NULL)
        {
                temp=NULL;
        }
        else
        {
                while(temp->data!=data)
                {
                printf("\n temp = %d",temp->data);
                temp2=temp;

                if(temp->data<data)
                {
                 temp=temp->right;
                }
                else
                {
                 temp=temp->left;
                }
                if(temp==NULL)
                break;
                }
                if(temp!=NULL)
                {
                if(temp->left==NULL&&temp->right==NULL)
                {
                 if(temp2->data<data)
                   temp2->right=NULL;
                   else
                   temp2->left=NULL;
                }
                else if(temp->left==NULL||temp->right==NULL)
                {
               printf("temp2 = %d",temp2->data);
                 if(temp2->data<data)
                    {
                      if(temp->right==NULL)
                        temp2->right=temp->left;
                    else
                        temp2->right=temp->right;
                    }
                    else
                    {
                    if(temp->right==NULL)
                        temp2->left=temp->left;
                    else
                        temp2->left=temp->right;
                    }
                free(temp);
            }
            else
            {

                //search largest left node
                temp3=temp->left;
                printf("\n temp 3  %d",temp3->data);
                while(temp3->right!=NULL)
                {
                    temp3=temp3->right;
                    printf("\ntemp3  %d",temp3->data);
                    getch();
                }
                //replace data of node to be deleted by largest left node
                temp->data=temp3->data;
                //delete largest left node
                delete_node(temp3,temp3->data);

            }
        }
        }
}
  • 4 Contributors
  • 3 Replies
  • 192 Views
  • 21 Hours Discussion Span
  • Latest Post Latest Post by Despairy

Dani AI

Generated

Short diagnosis: the code is getting tripped by pointer semantics and parent updates. Setting temp = NULL only changes the local variable; it never updates the parent or the caller’s root. Calling the deletion routine on an internal node pointer (as a way to remove the predecessor) also fails to update the predecessor’s parent. Comparing temp2->data to data to decide left/right is brittle (duplicates break it). These are the likely causes of the “nothing happens” or corruption you see.

A simple, robust pattern is to make the delete function return the (possibly new) subtree root so callers can assign it. That avoids parent-pointer juggling and makes the two-child case straightforward:

struct node *minValueNode(struct node *n) {
    while (n && n->left) n = n->left;
    return n;
}

struct node *delete_node(struct node *root, int key) {
    if (!root) return NULL;
    if (key < root->data)
        root->left  = delete_node(root->left,  key);
    else if (key > root->data)
        root->right = delete_node(root->right, key);
    else {
        if (!root->left) { struct node *t = root->right; free(root); return t; }
        if (!root->right){ struct node *t = root->left;  free(root); return t; }
        struct node *s = minValueNode(root->right);
        root->data = s->data;
        root->right = delete_node(root->right, s->data);
    }
    return root;
}

Practical debugging tips: run small, deterministic tests (delete leaf, one-child, two-children, root), print pointer addresses (not just values) to confirm which pointer is changed, and check with Valgrind for use-after-free and leaks. Remove getch() and excessive prints before testing real logic.

Regarding and : if you’re using an AVL/RB tree, deletion must also rebalance—this code is for an ordinary BST. For clarity and fewer bugs, prefer the recursive return-a-root approach or pass a struct node ** (double pointer) rather than trying to update parents by comparing values.

Recommended Answers

All 3 Replies

Member Avatar for WaltP

Care to give us specifics about the problem?

With the explanation you gave, the best answer is "then you did something wrong".

commented: ;) +2
Member Avatar for rubberman

If this is a balanced tree, then you need to rebalance when deleting the node. This is usually done recursively, which I don't think you are doing. Recursive algorithms are often MUCH simpler than trying to do the same thing in-line, though they may be a bit more resource intensive (stack memory and function call overhead mostly). Class exercise? Another approach is to walk the tree from left to right, creating a new tree, skipping the deleted node. If the tree isn't too big, this can be very effective, and possibly better (other than memory usage) than rebalancing the tree in-situ.

Member Avatar for Despairy

rubber how is rebuilding the tree could be any better than just deleting the node?
i thought deleting it in a non balanced tree would cost O(N)
and from a balanced (RB tree for instance) would cost O(logN)
whilst building a new tree is atleast NlogN

or did i missunderstodd the approach you are suggesting?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.