Fernanda Brum Lousada Fernanda Brum Lousada - 2 months ago 8
C Question

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

Answer

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)
Comments