### problem with binary search tree delete implementation

i'm having a problem implementing a binary search tree delete operation.

my logic for the deleteNode operation is this:

if value to delete is greater than value at the node, try do delete node at the right
else if value to delete is less than value at node, try do delete node to the left
else if value is equal, perform delete.

the 3 general cases are:
1.node is a leaf node (left & right child are null)
2.node has exactly one child that is null
3.node has two children (left & right child are not null)

now i am having a problem with implementing case 3,
this is how i want to implement case 3:

1.find the maximum at the left of the node to be deleted
2.if the maximum has no children
---i have 2 cases for this:

----a.maximum node is direct child (a left child)of the node i want to delete: if the maximum node is a child of the 'node to be deleted', replace that node with the maximum node found then assign the right child of the new node to the previous right child.

----b.maximum node is not a direct child of the node i want to delete: else if the maximum node is not a child of the node to be deleted, assign also the left child of the new node to the previous right child.
this is where i'm getting problem because if LINE 161 is not commented i am getting an infinite loop when printing the tree. but if i comment it out, two values are deleted-- the node that i want to delete and the node with the smallest value.

3. if the maximum has a left child- (i think there is no problem here)

can someone help me trace my mistake? thanks in advance.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204`` ``````#include #include struct charTreeNode{ char data; struct charTreeNode *left; struct charTreeNode *right; }; typedef struct charTreeNode CharTreeNode; typedef CharTreeNode *CharTreeNodePtr; void insertTreeNode(CharTreeNodePtr *rootPtr,char value); void inOrder(CharTreeNodePtr *rootPtr); void preOrder(CharTreeNodePtr *rootPtr); void postOrder(CharTreeNodePtr *rootPtr); //void deleteTreeNode(CharTreeNodePtr *rootPtr, char value); void deleteNode(CharTreeNodePtr *rootPtr,char value); CharTreeNodePtr findMax(CharTreeNodePtr *rootPtr); int main(){ CharTreeNodePtr rootPtr= NULL; insertTreeNode(&rootPtr,'d'); insertTreeNode(&rootPtr,'a'); insertTreeNode(&rootPtr,'c'); insertTreeNode(&rootPtr,'z'); insertTreeNode(&rootPtr,'m'); insertTreeNode(&rootPtr,'k'); insertTreeNode(&rootPtr,'j'); insertTreeNode(&rootPtr,'l'); insertTreeNode(&rootPtr,'n'); inOrder(&rootPtr); printf("\n"); preOrder(&rootPtr); printf("\n"); postOrder(&rootPtr); printf("\n"); deleteNode(&rootPtr, 'm'); inOrder(&rootPtr); printf("\n"); preOrder(&rootPtr); printf("\n"); postOrder(&rootPtr); printf("\n"); deleteNode(&rootPtr, 'k'); inOrder(&rootPtr); printf("\n"); preOrder(&rootPtr); printf("\n"); postOrder(&rootPtr); printf("\n"); deleteNode(&rootPtr, 'z'); inOrder(&rootPtr); printf("\n"); preOrder(&rootPtr); printf("\n"); postOrder(&rootPtr); printf("\n"); deleteNode(&rootPtr, 'a'); inOrder(&rootPtr); printf("\n"); preOrder(&rootPtr); printf("\n"); postOrder(&rootPtr); printf("\n"); return 0; } void insertTreeNode(CharTreeNodePtr *rootPtr,char value){ if(*rootPtr == NULL){ *rootPtr = malloc(sizeof(CharTreeNode)); if(*rootPtr != NULL){ (*rootPtr)->data = value; (*rootPtr)->left = NULL; (*rootPtr)->right = NULL; }else{ printf("Error: failed to allocate memory"); } } else{ if(value < (*rootPtr)->data){ insertTreeNode(&((*rootPtr)->left),value); } else if(value > (*rootPtr)->data){ insertTreeNode(&((*rootPtr)->right),value); } else{ printf("dup"); } } } void inOrder(CharTreeNodePtr *rootPtr){ if(*rootPtr != NULL){ inOrder(&((*rootPtr)->left)); printf("%c",(*rootPtr)->data); inOrder(&((*rootPtr)->right)); } } void preOrder(CharTreeNodePtr *rootPtr){ if(*rootPtr != NULL){ printf("%c",(*rootPtr)->data); preOrder(&((*rootPtr)->left)); preOrder(&((*rootPtr)->right)); } } void postOrder(CharTreeNodePtr *rootPtr){ if(*rootPtr != NULL){ postOrder(&((*rootPtr)->left)); postOrder(&((*rootPtr)->right)); printf("%c",(*rootPtr)->data); } } void deleteNode(CharTreeNodePtr *rootPtr,char value){ if(*rootPtr != NULL){ if(value == (*rootPtr)->data){ if((*rootPtr)->left == NULL && (*rootPtr)->right == NULL){ CharTreeNodePtr newPtr = (*rootPtr); (*rootPtr) = NULL; free(newPtr); } else if((*rootPtr)->right == NULL){ CharTreeNodePtr newPtr = (*rootPtr); (*rootPtr) = (*rootPtr)->left; free(newPtr); } else if((*rootPtr)->left == NULL){ CharTreeNodePtr newPtr = (*rootPtr); (*rootPtr) = (*rootPtr)->right; free(newPtr); } else{ CharTreeNodePtr newPtr; newPtr = (*rootPtr)->left; while(newPtr->right != NULL){ newPtr = newPtr->right; } //newPtr = findMax(&((*rootPtr)->left)); //if max is a leaf node if((newPtr->left == NULL) && (newPtr->right == NULL)){ //if max node is a child of root node if(newPtr == (*rootPtr)->left){ CharTreeNodePtr tempPtr; tempPtr = (*rootPtr); (*rootPtr) = newPtr; newPtr = NULL; (*rootPtr)->right = tempPtr->right; free(tempPtr); } else if(newPtr != (*rootPtr)->left){//else if max node is not a child of root node /*PROOOOOOBLEM*/ CharTreeNodePtr tempPtr; tempPtr = (*rootPtr); (*rootPtr) = newPtr; (*rootPtr)->right = tempPtr->right; //(*rootPtr)->left = tempPtr->left; newPtr = NULL; free(tempPtr); } } else if((newPtr->left != NULL) || (newPtr->right != NULL)){//if max has a child //if maxnode is a child of root node if((*rootPtr)->left == newPtr){ CharTreeNodePtr tempPtr; tempPtr = (*rootPtr); (*rootPtr) = newPtr; (*rootPtr)->right = tempPtr->right; (*rootPtr)->left = newPtr->left; newPtr = NULL; free(tempPtr); } else{//else if max node is not a child of root node CharTreeNodePtr tempPtr; tempPtr = (*rootPtr); (*rootPtr) = newPtr; (*rootPtr)->right = tempPtr->right; (*rootPtr)->left = tempPtr->left; newPtr = newPtr->left; free(tempPtr); } } } } else if(value < (*rootPtr)->data){ deleteNode(&(*rootPtr)->left,value); } else if(value > (*rootPtr)->data){ deleteNode(&(*rootPtr)->right,value); } } } CharTreeNodePtr findMax(CharTreeNodePtr *rootPtr){ CharTreeNodePtr temp = *rootPtr; while((temp->right != NULL)){ temp = temp->right; } return temp; }``````

Topic archived. No new replies allowed.