You are having some problem in passing the root pointer per parameter to the remove_node
This function is iterative, it has only one recursive call in the latter case. So you have to use two pointers. As we walk through the binary search tree until we find the element to be removed, let's keep the memory addresses of the current node ( current ) and the previous one ( previous ). But it is giving the root memory allocation error to the current pointer.
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");
}