arunmoezhi arunmoezhi - 1 month ago 23
C Question

Delete in Binary search tree in C

I have implemented BST in C. Insert and lookup works fine. But delete has issues when deleting the root node. I'm not able to free the pointer to the root node. I could if I pass it as a double pointer, but I wanted to keep the code simple without using double pointers. Here I do NOT have a head pointer which points to the root node. Should I use a head pointer to the root node?

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = malloc(sizeof(struct node));
node->data=data;
node->left=NULL;
node->right=NULL;
return(node);
}

static int lookup(struct node* node,int target)
{
if(node==NULL)
{
return(0);
}
else
{
if(target == node->data)
{
return(1);
}
else
{
if(target < node->data)
{
return(lookup(node->left,target));
}
else
{
return(lookup(node->right,target));
}
}
}
}


struct node* insert(struct node* node, int data)
{
if(node==NULL)
{
return(newNode(data));
}
else
{
if(data < node->data)
{
node->left =insert(node->left,data);
}
else
{
node->right=insert(node->right,data);
}
return(node);
}
}

struct node* delete(struct node* node, struct node* pnode, int target)
{
struct node* rchild;
struct node* rchildparent;
if(node==NULL)
{
return(pnode);
}
else
{
if(target == node->data)
{
if(node->left == NULL && node->right == NULL) //leaf node
{
if(pnode == NULL) //special case deleting the root node
{
free(node);
return(NULL);
}
if(pnode->left == node)
{
pnode->left = NULL;
}
else
{
pnode->right = NULL;
}
free(node);
return(pnode);
}
if(node->left ==NULL ) //one child
{
if(pnode == NULL) //deleting root having no left child
{
struct node* temp = node;
node = node->right;
free(temp);
return(node);
}
if(pnode->left == node)
{
pnode->left = node->right;
}
else
{
pnode->right = node->right;
}
free(node);
return(pnode);
}
if(node->right ==NULL ) //one child
{
if(pnode == NULL) //deleting root having no right child
{
struct node* temp = node;
node = node->left;
free(temp);
return(node);
}
if(pnode->left == node)
{
pnode->left = node->left;
}
else
{
pnode->right = node->left;
}
free(node);
return(pnode);
}

//two children case
rchild = node->right;
rchildparent=node;
while(rchild->left != NULL)
{
rchildparent=rchild;
rchild = rchild->left;
}
node->data=rchild->data;
if(rchildparent == node)
{
//rchildparent->right=rchild->right;
node->right=rchild->right;
}
else
{
//rchildparent->left=NULL;
rchildparent->left=rchild->right;
}
free(rchild);
if(pnode ==NULL) //root node
{
return(node);
}
return(pnode);
}
else
{
if(target < node->data)
{
delete(node->left,node,target);
return(node);
}
else
{
delete(node->right,node,target);
return(node);
}
}

}

}
void printinorder(struct node* node)
{
if(node == NULL)
{
return;
}
printinorder(node->left);
printf("%d\t",node->data);
printinorder(node->right);
}
int main()
{
clock_t start,end;
struct node* root = newNode(3);
insert(root,7);
insert(root,7);
insert(root,7);
printinorder(root);
printf("\n");
root = delete(root,NULL,6);
printinorder(root);
printf("\n");
}


EDIT:
Fixed the code as per @
modifiable lvalue
suggestion. Now is there a way I can improve the delete logic?

Seb Seb
Answer

I'd return the head node from delete, and manage the head in your main function like: root = delete(root, NULL, 10);, and I'd do the same for insert: root = insert(root,/*...*/);, as it sort of half looks like you've done...