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;
}

---

So... Is the code fine then? :P