Programmer - Fixing pointers in binary tree delete function (node with 2 children)

Programmer Question

Hi,

I'm a having a little trouble thinking how the hell do I fix the appropriate pointers when trying to delete a node from a binary tree where that node has 2 children.

I understand the basic concept and I'm basically just having trouble fixing the pointers...

So, basically, my delete function is mostly done and every case is already working (as far as my extensive testing go, everything worked OK), I'm only missing the case node with 2 children. Let's say we are inside the else if that deals with that case:

I will have 2 pointers there, currPtr which holds the node to be deleted, prevPtr which holds the parent node. I also have a variable named fromLeft which defines if the currPtr parent comes from the left or right pointer on prevPtr. Then, I have a call to another function named extractMin(Tree *t) which extracts the lowest value in the tree. If I cann this function with currPtr->right as argument, the successor of currPtr is going to be extracted from the tree (the function will deleted it from tree, fix the pointers and return the node pointer). The successor pointer is going to be saved on tempPtr.

Here's the structure of my tree:

typedef int TreeElement;

typedef struct sTree {
   TreeElement item;

   struct sTree *left;
   struct sTree *right;
} Tree;

And the code for the extract function:

Tree *extractMin(Tree *tree) {
    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if(prevPtr) prevPtr->left = currPtr->right;

    // inorder successor
    return currPtr;
}

The code above is missing the case here the tree only has one node, the root node, it won't work properly and it also doesn't check if the tree has any nodes at all but, it works when a tree has a few nodes.

So, how do I fix the necessary pointers on the else if for the node deletion? Also, remember that the left and right pointers on the tree nodes will always be pointing somewhere or be NULL.

By the way, I want to do this iterative.