CODEWITHSUNDEEP
cpointersbinary-search-tree
Fernanda Brum Lousada
Fernanda Brum Lousada

Reputation: 371

Why pointer is not zeroing node of BST after remove function call?

Have a recursive remove function for BST that isn't zeroing a pointer to a leaf node.

bool removeNode(Node* tree, int key)
{
    bool removed = false;

    if (tree)
    {
        if (key < tree->key)
        {
            removeNode(tree->left, key);
        }
        else if (key > tree->key)
        {
            removeNode(tree->right, key);
        }
        else // this node is the key
        {
            if (!tree->left && !tree->right) // leaf
            {
                free(tree);
                tree = 0;
            }
            else if (!tree->left)
            {
                *tree = *tree->right;
            }
            else if (!tree->right)
            {
                *tree = *tree->left;
            }
            else // this node has 2 children
            { 
                Node* paux = tree->left;

                if (paux->right)
                {
                    while (paux->right)
                    {
                        paux = paux->right;
                    }
                }

                tree->key = paux->key;
                tree->left = paux->left;
            }

            removed = true;
        }
    }

    return removed;
}

I use

Node* node = (Node*)malloc(sizeof(Node));

to allocate memory. My leaf's address is correctly zeroed, but when it returns to the previous call, the address remains still the same. If the address was zeroed, why does it return to the previous value? The change should have affected the pointer... shouldn't it?

Data structures and related functions:

typedef struct Node
{
    int key;
    struct Node* left;
    struct Node* right;
} Node;

// init a binary tree
void init(Node** tree, int key)
{
    *tree = (Node*) malloc(sizeof(Node));

    (*tree)->key = key;
    (*tree)->left = 0;
    (*tree)->right = 0;
}

// insert at binary tree
bool insert(Node** tree, int key)
{
    bool inserted = false;

    if (!*tree)
    {
        init(&*tree, key);
    }
    else
    {
        Node* node = (Node*)malloc(sizeof(Node));
        node->key = key;
        node->left = 0;
        node->right = 0;

        Node* paux = *tree;
        Node* root = paux;

        while (paux != 0)
        {
            root = paux;

            if (key < paux->key)
            {
                paux = paux->left;
            }
            else
            {
                paux = paux->right;
            }
        }

        paux = node;
        if (key < root->key)
        {
            root->left = paux;
        }
        else
        {
            root->right = paux;
        }

        inserted = true;
    }

    return inserted;
}

void print(Node* tree)
{
    if (tree != 0)
    {
        printf("%d  ", tree->key);

        print(tree->left);
        print(tree->right);
}

Upvotes: 1

Views: 60

Answers (3)

4386427
4386427

Reputation: 44274

As you want to be able to change tree inside the function you need a double pointer.

Instead of 

bool removeNode(Node* tree, int key)

you need

bool removeNode(Node** tree, int key)
                    ^^

That also means that you need to change the way you access tree inside the function.

Also see: https://stackoverflow.com/a/39436538/4386427 - it is the same problem

Upvotes: 3

eyalm
eyalm

Reputation: 3366

The problem you encounter happens because the function is not able to modify the input pointer. The pointer itself is passed by value.

Think of a function that increments an integer. The trivial implementation will not work as the argument is passed "by value".

void inc(int x)
{
    x++;
}

you can fix this sample by passing it by reference (a pointer)

void inc(int *x)
{
    (*x)++;
}

so, if you want to be able to nullify the pointer from within the function pass a pointer to the pointer:

bool removeNode(Node **tree, int key)

Upvotes: 4

cxw
cxw

Reputation: 17041

removeNode() has its own copy of tree, so changes to the actual value of tree itself are not visible outside removeNode(). One option is to make tree a Node **, as others have suggested. Another option is to refactor so that you have the parent's pointer available at the point where you want to free the node. For example, the parent could be passed as another parameter to removeNode(), or your code could test one level deeper while processing. Then you could do free(parent->left); parent->left=0; or some such.

Upvotes: 1

Related Questions