Can't delete tree node

[oleg9419]

Hello it seems that I can't delete a node without children, and I have no idea why .
Can you please help me ?

#define TRUE 1
#define FALSE 1

typedef struct binary_tree_nodes_t
{
	struct binary_tree_nodes_t* right;
	struct binary_tree_nodes_t* left;
	unsigned char letter;

}binary_tree_nodes_t;

typedef struct binary_tree_t
{
	binary_tree_nodes_t* root;
	int size;

}BinaryTree;

static binary_tree_nodes_t* search_node(binary_tree_nodes_t* node, unsigned char letter)
{
	if(node != NULL)
	{
		char c = node->letter;

		if(c == letter)        return node;
		else if(c > letter) return search_node(node->left, letter);
		else 		      return search_node(node->right, letter);
	}
	else return (binary_tree_nodes_t*)NULL;
}

binary_tree_nodes_t* search(BinaryTree* tree, unsigned char letter)
{
	return search_node(tree->root, letter);
}

int delete(BinaryTree* tree, unsigned char letter)
{
	if(tree != NULL)
	{
		--tree->size;
		binary_tree_nodes_t* root = search_node(tree->root, letter);


		//3 cases to search
		if(root->left == NULL && root->right == NULL) // no child case
		{
			free(root);
			root = NULL;
		}
		return TRUE;
	}
	else return FALSE;
}

void insert(BinaryTree* tree, unsigned char letter)
{
	tree->root = insert_node(tree->root, letter);
	++tree->size;
}

static binary_tree_nodes_t* insert_node(binary_tree_nodes_t* root, unsigned char letter)
{
	if(root == NULL)
		root = new_node(letter);

	else if(letter >= root->letter)
		root->right = insert_node(root->right, letter);

	else
		root->left = insert_node(root->left, letter);

	return root;
}

void traverse(BinaryTree* tree)
{
	if(tree != NULL) traverse_root(tree->root);
}

static void traverse_root(binary_tree_nodes_t* node)
{
	if(node != NULL)
	{
		traverse_root(node->right);
		printf("%c\n", node->letter);
		traverse_root(node->left);
	}
}

should my search_node function return this : binary_tree_nodes**
so I can get the address of pointer , is this causing my problem ?

[Peter87]

Your function doesn't handle the case when the left and/or right child is not null.

Your search_node function doesn't return anything on line 26 and 27.

You also need to change one of the child pointers (left or right) of the parent node because you don't want any pointers to point to the node after you have freed it.

[oleg9419]

first, I want to handle only this case , then I'll take care of others.
search_node will always run through the binary tree till it finds a null node and then it goes all the way back.( i could write return but nothing would change)

I could add more functions if you need them here.

[dhayden]

I'll repeat what Peter87 said: search_node() doesn't return anything on lines 26 and 27. It calls itself recursively but it then ignores the returned value.

In your delete function, line 49 sets the local variable root to NULL, but whatever pointer (tree->root or some node's left or right pointer) pointed to the node is still set, creating a dangling pointer.

[oleg9419]

1.I edited the return thing . but please explain , it worked perfectly if I didn't write any return on line 26 and 27.

2.so the solution to my problem would be to somehow create a double pointer function and take care of it ?

[dhayden]

it worked perfectly if I didn't write any return on line 26 and 27.

It worked by accident. For example, the return value may have been stored in a CPU register so the right value happened to be there.

The thing you have to realize with recursive functions is that each call has different parameters, different local variables and a different return value.

so the solution to my problem would be to somehow create a double pointer function and take care of it ?

You could have search_node return a reference to the pointer:

static binary_tree_nodes_t* &search_node(binary_tree_nodes_t* &node, unsigned char letter)
{
	if (node != NULL)
	{
		char c = node->letter;

		if(c == letter)        return node;
		else if(c > letter) return search_node(node->left, letter);
		else 		      return search_node(node->right, letter);
	}
	else return node;
}

[Peter87]

dhayden wrote:

You could have search_node return a reference to the pointer

If you use C, and not C++, you can't use references because C doesn't have them. What you could do instead is to pass a pointer to the pointer.

[oleg9419]

This is still wrong , because I don't want to pass directly the tree's root node as parameter in the main function,.
I don't want to mess my main with this ex: delete(&tree,'a')

int delete(BinaryTree* tree, unsigned char letter)
{
	if(tree != NULL)
	{
		--tree->size;
		binary_tree_nodes_t** root = search_node(&tree->root, letter);


		//3 cases to search
		if((*root)->left == NULL && (*root)->right == NULL) // no child case
		{
			free((*root));
			(*root) = NULL;
		}

		return TRUE;
	}
	else return FALSE;
}

static binary_tree_nodes_t** search_node(binary_tree_nodes_t** node, unsigned char letter)
{
	if((*node) != NULL)
	{
		char c = (*node)->letter;

		if(c == letter)      return node;
		else if(c > letter)  return search_node(&(*node)->left, letter);
		else 				 return search_node(&(*node)->right, letter);
	}
	else return (binary_tree_nodes_t**)NULL;
}

binary_tree_nodes_t* search(BinaryTree* tree, unsigned char letter)
{
	return *search_node(&tree->root, letter);
}

I think it's wrong because after executing this line

free((*root));

does not do anything to my unsigned char data, it still stays there , only after setting

*root = NULL

the program will output what I want but this is memory leak.

[dhayden]

you can't use references because C doesn't have them.

Since this is a C++ site, I assumed that you were talking about C++.

I think it's wrong because after executing this line
free((*root));
does not do anything to my unsigned char data, it still stays there

That's okay. When you free memory, the program doesn't necessarily erase it. It just marks the memory as available for reuse.

I don't want to pass directly the tree's root node as parameter in the main function,.

That's understandable. The way to handle it is to have two functions:

void deleteFromNode(binary_tree_nodes_t **node, char ch);
void delete(BinaryTree *tree, char ch)
{
    deleteFromNode(&tree->root, ch);
}