Cfrgtkky

I'm performing binary tree deletion in c.I was trying out few methods interestingly this weird situation came.

void Delete(){

    struct BinaryTree* ptr = root;

    int element;

    printf("Enter element to delete : ");

    scanf("%d",&element);

    while(ptr){

        if(element>ptr->data)

            ptr = ptr->right;

        else if(element<ptr->data)

            ptr = ptr->left;

        else

            break;

    }

    if(ptr->left && ptr->right){

        struct BinaryTree **smallest = &(ptr);

        smallest = &((*smallest)->right);

        while((*smallest)->left){

            smallest = &((*smallest)->left);

        }

        ptr->data = (*smallest)->data;

        free(*smallest);

        *smallest = NULL;



    } else if(ptr->left){

            /*rest cases*/

    }



}

The above code works and it sets the the NODE to NULL.

But when i do this procedure in this way it doesn't set to NULL.

if(ptr->left && ptr->right){

    struct BinaryTree *smallest = ptr;

    smallest = smallest->right;

    while(smallest->left){

        smallest = smallest->left;

    }

    ptr->data = smallest->data;

    struct BinaryTree **refsmall = &smallest;

    free(*refsmall);

    *refsmall = NULL;

}

Aren't these two methods are same? If not can someone explain me how they are different?Why the first method work and second didn't?

You should avoid using global variables in your code. If you really want to use globals the first version of delete should look like this:

void Delete(){

    /* at some point you will need to change the 'real' root, not the copy of it */

    struct BinaryTree **ptr = &root;

    int element;

    printf("Enter element to delete : ");

    scanf("%d",&element);

    while(*ptr){

        if(element > (*ptr)->data)

            ptr = &(*ptr)->right;

        else if(element < (*ptr)->data)

            ptr = &(*ptr)->left;

        else

            break;

    }

    if((*ptr)->left && (*ptr)->right){

        struct BinaryTree **smallest = ptr;

        smallest = &(*smallest)->right;

        while((*smallest)->left){

            smallest = &(*smallest)->left;

        }

        (*ptr)->data = (*smallest)->data;

        free(*smallest);

        *smallest = NULL;



    } else if((*ptr)->left){

            /*rest cases*/

    }

}

In the first version you would not be able to delete the root.

struct node {

        struct node *l,*r;

        int data;

        };



void delnode(struct node **pp, int data)

{

struct node *del, *l,*r;



        // Walk the tree

while(*pp) {

        if ((*pp)->data < data) {pp = &(*pp)->l; continue;} 

        if ((*pp)->data > data) {pp = &(*pp)->r; continue;}

        break; // found it!

        }

if (!*pp) return; // not found



del = *pp;

l = del->l;

r = del->r;

        // If only one child it wil take del's place.

if (!r) *pp = l;

else if (!l) *pp = r;



        // del has two children.

        // pick one (R) child, and append the (L) other onto its (Leftmost) shoulder

else    {

        *pp = r;

        for (pp= &del->r; *pp; pp=&(*pp)->l) {;} // find Leftmost NULL pointer in the R tree

        *pp = l;

        }

free(del);

}