# Thread: Deleting from Binary search trees

1. ## Deleting from Binary search trees

Hey there... can anyone suggest code for deleting a term from a tree.. I have a base code for searching the tree... we have to take into account whether or not the term to be deleted has children or not...

2. If what you are going to delete has no children, then the pointer to the node you are deleting should be set to NULL. If the node you are deleting has one child node/subtree, then the pointer to the node you are deleting should be set to the node/subtree. If the what you are deleting has two child nodes/subtrees, then the pointer to the node you are deleting can be set to one of the subtrees, left or right it doesn't matter, and you can then reinsert the remaining node/subtree back into the root of the tree using whatever add/insert function you have created to insert a new node into the tree.

3. Any suggested code for that? just not sure how to do it code wise... thanks for replying!

4. Try This one:
Code:
```tree dtree(tree root,int key)
{
tree p,p2;
if(!root) return root;

if((root->e.id)==key) /* delete root */
{
if(root->lift == root->right)
{
free(root);
return NULL;
}
/* or if one subtree is null */
else if(root->lift ==NULL)
{
p=root->right;
free(root);
return p;
}
else if(root->right ==NULL)
{
p= root->lift;
free(root);
return p;
}
/* or if both subtree are ther */
else
{
p2=root->right;
p=root->right;
while(p->lift) p=p->lift;
p->lift = root->lift;
free(root);
return p2;
}
}

if(root->e.id < key) root->right = dtree(root->right,key);
else root->lift= dtree(root->lift,key);
return root;
}```
see you

5. ## same problem

how would you write it if you were using strings and files in the tree?
i.e. if the actual nodes of the tree contains a string of words
if you know what i mean.

6. ## code

here's a program i wrote but i need help correcting it

Code:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 40

typedef struct treenode
{
char word[SIZE];
int count;

struct treenode *left;
struct treenode *right;
} treenode;  //structure

treenode* insert(treenode*, char*);
void inorder(treenode*);
void preorder(treenode*, FILE*);
void check_choice(treenode* tree, char);
void freetree(treenode*);
int deletenode(treenode*, char);

//begin main function
int main()
{
char	str[30];
FILE* fptr;
int check =0;
char ch;

treenode* root =NULL;

if ( (fptr = fopen("btree.txt","r")) == NULL)
{
fprintf(stderr, "Error in opening file test.txt");
return(0);
}

while(fscanf(fptr, "%s", str) != EOF)
root = insert(root, str);

scanf(" %c", &ch);

while ((ch != 'e') && (ch != 'E'))
{
check_choice(root, ch);
scanf(" %c", &ch);
}

fclose(fptr);

if ( (fptr = fopen("btree.txt","w")) == NULL)
{
fprintf(stderr, "Error in opening file test.txt for writing");
return(0);
}
preorder(root, fptr);

return(1);
}

treenode* insert(treenode* root, char word[30])
{
if(root == NULL)
{
root = (treenode *) malloc(sizeof(treenode));
strcpy(root->word, word);
root->left = NULL;
root->right = NULL;
root->count = 1;
}

else
{
if((strcmp(word,root->word))==0)
{
root->count++;
}
else if((strcmp(word,root->word)) < 0)
{
root->left = insert(root->left, word);
}
else if((strcmp(word,root->word)) > 0)
{
root->right = insert(root->right, word);
}
}
return(root);
}

void search(treenode *root, char *term)
{
int l;

if (root == NULL)
{
return;
}
else if ((l = strcmp (root->word, term)) == 0)
{
printf("Term found in tree\n");
return;
}
else if	(l > 0)
search(root->left, term);
else
search(root->right, term);
}

void inorder(treenode* root)
{
if(root != NULL)
{
inorder(root->left);
printf("\n %s %d",root->word, root->count);
inorder(root->right);
}
}

void  preorder(treenode *root, FILE *fptr)
{
if (root != NULL)
{
preorder(root->left, fptr);
fprintf(fptr, "%s ",root->word);
preorder(root->right, fptr);
}
}

{

printf("\n\tExit program (e)\n");
printf("\tDisplay tree (d)\n");
printf("\tSearch tree for string (s)\n");
printf("\tAdd new string to tree (a)\n");
return;
}

void check_choice(treenode *tree, char choice)
{
char term[WORD_SIZE];

switch(choice)
{
case 'e' : printf("Exiting ...\n");
break;
case 'd' : inorder(tree);
break;
case 's' : printf("Please enter search term\n");
scanf ("%s", term);
search(tree, term);
break;
scanf ("%s", term);
tree = insert(tree, term);
break;
case 'b' : printf("please enter a term to be deleted\n");
scanf("%s" , term);
del(tree, term);
break;
}
}

//begin function to delete a value from the tree

treenode* del(treenode* tree, char tofind)
{
char term=0;
treenode* parent=NULL, *deleted=NULL, *suc, *word;

if (tree=NULL)
printf("tree empty\n");
term= search(tree, term);

if(!term)
printf("string %s is not in tree\n", term);

else
{
if(root->leftptr==NULL && root->rightptr==NULL)
{
if(parent==NULL)
tree=parent;
else if(parent->leftptr==deleted)
parent->leftptr=NULL;
else
parent->rightptr=NULL;
free(deleted);
}

else if (deleted->leftptr==NULL && deleted->rightptr!=NULL)
{
if(parent==NULL)
tree=deleted->rightptr;
else if (parent->leftptr==deleted)
parent->leftptr=deleted->rightptr;
else
parent->rightptr=deleted->leftptr;

free(deleted);
}

else if(deleted->leftptr!=NULL && deleted-.rightptr==NULL)
{
if (parent==NULL)
tree=deleted->leftptr;

else if(parent->leftptr==deleted->leftptr)
parent->leftptr=deleted->leftptr;
else
parent->rightptr=deleted->leftptr;
free(deleted);

}

else
{
parent=deleted;
suc=deleted->rightptr;
while(suc->leftptr!=NULL)
{
parent=suc;
suc=suc->leftptr;
}

strcpy(deleted->word,suc->word);
deleted=suc;
parent->rightptr=suc->rightptr;
parent->leftptr=suc->leftptr;
free(suc);
}

}
return(tree);
}```

the program is right without the delete function,so can anyone correct it for me?

7. Code:
```char term=0;
treenode* parent=NULL, *deleted=NULL, *suc, *word;

if (tree=NULL)
printf("tree empty\n");
term= search(tree, term);```
I'm not sure why but you end up searching for term=0 here and
I don't understand why toFind is a charecter and not a c style string when your tree holds strings.

The easiest way to delete from a tree is to do it recursivly.
So you have have a prototype for your function like

treenode* del(treenode** tree, char* toFind);

And then you will probably have a line such as
Code:
```int t = strcmp(toFind, (*tree)->word);
if (t < 0)
*tree = del((*tree)->left, toFind);
else if (t > 0)
*tree = del((*tree)->right, toFind);
else {
/* handle the three cases */
Probably the easiest way is to draw a picture of each one
the only real tough one is when (*tree)->left != NULL and
(*tree)->right != NULL and for that one you want to change
*tree to the least valued node from the right tree
(the successor) and  then  delete successor of the
right  tree.
}```