How would you improve this binary tree delete function?

• 02-19-2010
Nazgulled
How would you improve this binary tree delete function?
Hi,

Last year I posted on this forum about a binary tree delete function, but I gave up on what I was doing (it was for university) but now I'm at it again. I tried to understand my last year's code and I came to the conclusion that it was very buggy and it was not deleting the nodes correctly.

I just finished a new implementation of the delete function (with a simpler data structure just so I don't confuse things-- just an int instead of a couple of strings-- which I believe is working fine. I tested every case I remember and it seemed to fix all the pointers correctly.

But I'm looking for opinions on how to improve this code. And I know the code can be improved in a number of ways but I'm looking for improvements given some restrictions I want to impose. Maybe some of them don't make much sense to you, but I know why I want do it that way, don't worry about it.

Here's what I "don't care" to improve on this code:
• This version is iterative, someone already suggested me to do it recursively but I don't want to. I prefer iterative as I find the code easier to understand, I also avoid stack problems like this.
• I'm not looking for syntax improvements but more like "remove a piece of a code and replace it by a different one" type of thing, maybe it does the same thing but with less code or maybe with more simplified code.
• I'm using the inorder successor when deleting a node with 2 children to use as replacement for the node to be deleted. I know this can produce an unbalanced tree but I'm doing one thing at the time. Right now, I'm simply doing a binary tree and not AVL tree.
• The tree structure is not subject to change. If possible, the function signatures should not be changed too, unless it really simplifies the code (in a way I can understand it lol).

That's it, here's the relevant code:

Code:

```typedef int TreeElement; typedef struct sTree {   TreeElement item;     struct sTree *left;   struct sTree *right; } Tree; Tree *extractMin(Tree **tree) {         if(!tree) return NULL;                 Tree *prevPtr = NULL;         Tree *currPtr = *tree;                 while(currPtr->left) {                 prevPtr = currPtr;                 currPtr = currPtr->left;         }                 if(prevPtr) prevPtr->left = currPtr->right;         else *tree = NULL;                 // inorder successor         return currPtr; } int delete(Tree **tree, TreeElement item) {         if(!*tree) return 1;                 Tree *prevPtr = NULL, *tempPtr = NULL;         Tree *currPtr = *tree;         // loops through the nodes until it finds the one to delete         while(currPtr) {                 // go to the left, right or was the element to delete found?                 if(item < currPtr->item) {                         prevPtr = currPtr;                         currPtr = currPtr->left;                 } else if(item > currPtr->item) {                         prevPtr = currPtr;                         currPtr = currPtr->right;                 } else {                         // handles node with no children or with one child                         if(!currPtr->left || !currPtr->right) {                                 /* get the child to replace the deleted node with                                   it will be null if there are no children */                                 tempPtr = currPtr->left ? currPtr->left : currPtr->right;                                                                 // fix the tree root or a different node?                                 if(!prevPtr) {                                         *tree = tempPtr;                                 } else {                                         // fix the left or right pointer in the parent node?                                         if(prevPtr->left == currPtr) prevPtr->left = tempPtr;                                         else prevPtr->right = tempPtr;                                 }                         }                         // handles node with two children                         else if(currPtr->left && currPtr->right) {                                 // extract inorder successor                                 tempPtr = extractMin(&(currPtr->right));                                                                 // fix the successor left pointer                                 tempPtr->left = currPtr->left;                                                                 // fix the successor right pointer                                 if(currPtr->right != tempPtr) tempPtr->right = currPtr->right;                                 else tempPtr->right = NULL;                                                                 // fix the left or right pointer in the parent node?                                 if(prevPtr->left == currPtr) prevPtr->left = tempPtr;                                 else prevPtr->right = tempPtr;                         }                                                 free(currPtr);                                                 return 0;                 }         }                 return 1; }```
• 02-20-2010
Nazgulled
So... Is the code fine then? :P