Thread: Delete Binary Tree Node

Hello,

After about a week of trying to figure out how to write a function that would take into consideration all aspects of deleting a node from a binary tree... I succeeded. After writing the function, I looked at it, and said to myself, "There has to be a way to make this easier to write and easier to read."

Since I am teaching myself, I wanted the communities input as to how I could have approached this differently, how I can reduce my code, if necessary (I have a feeling I could have used recursion), comments, critisism, etc. Below is the code:

Code:

void delete_node(BTREE *node, int value)
{
	BTREE *current = NULL, *del_node = NULL, *child = NULL;
	BTREE *parent = NULL, *x = NULL;
	current = node; 		
	
	while (current != NULL) {		
		if (value == current->num) {
		del_node = current;
		//case 1: node is a leaf (no descendants)
			if ((del_node->left == NULL) && (del_node->right == NULL)) {
				//if the node to delete is to the left of root
				if (parent->left == del_node) {
					parent->left = NULL;
					free(del_node);
					printf("Node deleted\n");
					break;
				}
				//if the node to delete is to the right of root
				else if (parent->right == del_node) {
					parent->right = NULL;
					free(del_node);
					printf("Node deleted\n");
					break;
				}
			}
		//case 2: node has one child
			else if ((del_node->left == NULL) || (del_node->right == NULL)) {
				printf("Node has one child\n");
				//if the node to delete is to the left of root
				if (parent->left == del_node) {
					if (del_node->left != NULL) {
						child = del_node->left;
						parent->left = child;
						free(del_node);
						break;
					}
					else if (del_node->right != NULL) {
						child = del_node->right;
						parent->left = child;
						free(del_node);
						break;
					}
				}
				//if the node to delete is to the right of root
				else if (parent->right == del_node) {
					if (del_node->left != NULL) {
						child = del_node->left;
						parent->right = child;
						free(del_node);
						break;
					}
					else if (del_node->right != NULL) {
						child = del_node->right;
						parent->right = child;
						free(del_node);
						break;
					}
				}						
			}
		//case 3: node has two children	
			else if ((del_node->left != NULL) && (del_node->right != NULL)) {
				printf("Node has two children\n");
				x = del_node;
				//if the node to delete is root
				if (parent == NULL) {
					child = del_node->right;
					if (child->left == NULL) {
						child->left = del_node->left;
						free(del_node);
						break;
					}
					else {
						while (child->left != NULL) {
								parent = child;
								child = parent->left;
						}
						x->num = child->num;
						parent->left = child->right;
						del_node = child;
						free(del_node);
						break;
					}						
				}
				//if the node to delete is to the left of root
				else if (parent->left == del_node) {
					child = del_node->right;
					if (child->left == NULL) {
						parent->left = child;
						child->left = del_node->left;
						free(del_node);
						break;
					}
					else {
						while (child->left != NULL) {
								parent = child;
								child = parent->left;
						}
						x->num = child->num;
						parent->left = child->right;
						del_node = child;
						free(del_node);
						break;
					}
				}
				//if the node to delete is to the right of root
				else if (parent->right == del_node) {
					child = del_node->right;
					if (child->left == NULL) {
						parent->right = child;
						child->left = del_node->left;
						free(del_node);
						break;
					}
					else {
						while (child->left != NULL) {
								parent = child;
								child = parent->left;
						}
						x->num = child->num;
						parent->left = child->right;
						del_node = child;
						free(del_node);
						break;
					}
				}
			}		
		}
		//if value is less than the node's value - go left
		else if (value < current->num) {
			parent = current;
			current = current->left;
		}
		//if value is greater than the node's value - go right
		else {
			parent = current;
			current = current->right;
		}
	}		
}

Thank you for taking the time to read this thread and provide any comments.

Considering everything is true in the beginning, parent isn't pointed to anything, but you use parent->left. Doesn't this crash your program?

Reducing your code = using more functions

When you have the same code, but just change "left" with "right", you can use a function and have a pointer as a parameter. Then you just pass either left or right. So it would be something like

Code:

if (parent->right == del_note)
   del_single_child(del_note);
else
   del_single_child(del_note);

This also help people understand more easily your code. Reading "del_single_child" they have all the information they need. If they want more, they can read the actual code of the function (rather sub-function).

Thanks for the reply C_ntua,

After I posted the code, I realized there were 2 cases that would occur that I hadn't accounted for:

If the root node only had one child and if the root node was the only node in the tree.

When I performed a test, the program did crash, because parent was initialized to NULL. Once I took those cases into account, I changed the code a little bit and it all seems to be working ok now.

I see what your saying about reducing the code by using more functions, but I think I would have to implement more than one function in the case of:

Code:

if (parent->right == del_note)
   del_single_child(del_note);
else
   del_single_child(del_note);

I think something like:

Code:

if (parent->right == del_note)
   del_single_child_right(del_note);
else
   del_single_child_left(del_note);

would work better only because I have to reinitialize parent->left or parent->right differently depending on if I go left or right.

I remember reading somewhere on the internet that if you write the function iteratively, the code's performance is better than if you write the function recursively. Something to do with each recursive functions' call being pushed and popped off the stack. Is it better to have more functions that use an iterative technique to reduce my code or better to use recursion?

iMalc,

Thanks for the reply. When I started to think about how I could implement recursion, I came to a problem. In my original code, I knew how to handle each case because I knew which node was the parent of the node I was going to delete. When I think about using recursion, for example, if I had a sample tree:

Code:

       90
     /    \
    /      \
   X       140
         /     \
        /       \
      125         175
    /     \     /     \
   /       \   /       \
  X         X X         X

and I wanted to delete the number 140, and I used recursion to move from 90 to 140, how would I keep account of the pointer that got me there? I know once I found the node I could just delete it, but how would the parent->right pointer get updated with the new node it should point to?