# Deleting from Binary search trees

• 03-13-2002
lenicush
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...
• 03-13-2002
hk_mp5kpdw
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.
• 03-13-2002
lenicush
Any suggested code for that? just not sure how to do it code wise... thanks for replying!
• 03-13-2002
talal*c
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
• 03-13-2002
seeks
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. :(
• 03-13-2002
seeks
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 menu(); 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);   menu();   scanf(" %c", &ch);     while ((ch != 'e') && (ch != 'E'))         {         check_choice(root, ch);                menu();         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)                 {                 printf("Term not found\n");                        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);                 }         } void menu()         {                 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;                 case 'a' : printf("Please enter term to be added\n");                           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?:confused:
• 03-13-2002
Unregistered
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. }```