Pointer problem - remove element in a binary search tree

Question

Having some problem passing the root pointer per parameter to the function remove_node.

This function is iterative, it has only one recursive call in the latter case. Therefore, it is necessary to use two pointers. As we walk through the binary search tree until we find the element to be removed, we keep the memory addresses of the current node (Current) and the previous(Previous). But you are giving error in assigning the root memory address to the pointer Current.

Thank you!

#include <stdio.h>
#include <stdlib.h>

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


Node* get_new_node(int data)
{
 Node* new_node = (Node *) malloc(sizeof(Node));
 new_node->data = data;
 new_node->left = new_node->right = NULL;
 return new_node;
}    


Node* insert(Node *root, int data)
{
 if(root == NULL){
     root = get_new_node(data);
 }else if(data <= root->data){
     root->left = insert(root->left, data);
 }else if(data > root->data){
     root->right = insert(root->right, data);
 }
 return root;
}

int get_min_value(Node *root)
{
 while(root->left != NULL)
    root = root->left;
 return root->data;
}

void remove_node(Node *root, int value)
{
 int is_remove_node_a_left_child;
 int value_min_tmp;
 Node* previous, current;
 Node* root_min_tmp;

 previous = NULL;
 current = root;

//finding the node to be removed
 while(value != current->data)
 {
    previous = current;
    if(value < current->data)
    {
        current = current->left;
        is_remove_node_a_left_child = 1;
    }else
    {
        current = current->right;
        is_remove_node_a_left_child = 0;
    }
 }
//current is now pointing to the node to be removed, and previous, to its parent

//cases:
 if((current->left == NULL) && (current->right == NULL))
 {//the remove node has no child
    if(is_remove_node_a_left_child == 1)
        previous->left = NULL;
    else
        previous->right = NULL;
    free(current);
 }else if((current->left == NULL) && (current->right != NULL))
 {//the remove node has only a right child
    if(is_remove_node_a_left_child == 1)
        previous->left = current->right;
    else
        previous->right = current->right;
    free(current);
 }else if((current->left != NULL) && (current->right == NULL))
 {//the remove node has only a left child
    if(is_remove_node_a_left_child == 1)
        previous->left = current->left;
    else
        previous->right = current->left;
    free(current);
 }else
 {//the remove node has a left and a right child
    value_min_tmp = get_min_value(current->right);
    remove_node(current->right, value_min_tmp);
    current->data = value_min_tmp;
 }

}


void show_bst_in_order(Node* root)
{
 if(root == NULL)
    return;
 show_bst_in_order(root->left);
 printf("%d ", root->data);
 show_bst_in_order(root->right);
}


int main(){
 int return_value;
 Node *root = NULL;

 root = insert(root, 10);
 root = insert(root, 3);
 root = insert(root, 1);
 root = insert(root, 7);
 root = insert(root, 19);
 root = insert(root, 25);
 root = insert(root, 30);
 root = insert(root, 6);
 root = insert(root, 4);

 printf("Binary search tree in order:\n");
 show_bst_in_order(root);
 printf("\n");

}

Answer 1

You have only declared the Previous variable as a pointer. The Current variable is of the struct Node type. To declare the two variables as pointers do as follows:.

void remove_node(Node* root, int value){
    ....

    Node* previous, *current; // <---------- Modifique aqui
    Node* root_min_tmp;
    previous = NULL;
    current =root;
    .....
}