Delete Binary Tree Node

This is a discussion on Delete Binary Tree Node within the C Programming forums, part of the General Programming Boards category; Hello, After about a week of trying to figure out how to write a function that would take into consideration ...

  1. #1
    Registered User matrixx333's Avatar
    Join Date
    Mar 2009
    Posts
    67

    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.

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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).

  3. #3
    Registered User matrixx333's Avatar
    Join Date
    Mar 2009
    Posts
    67
    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?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    By far the greatest simplification you can make to that code would be to use recursion and have the code pass a pointer-to-a-pointer to the node rather then just a single-pointer, so that none of the code has to know whether the node being deleted comes from a left or a right of a node or from the root. Instead it just NULLs whatever was passed in.

    This is a minimal example to demonstrate that concept, and is meant to contain memory leaks etc, but the finished code needn't be more than about two to three times this size.
    Code:
    void delete_node(BTREE **node, int value)
    {
        if (*node == NULL)
            return;
        else if ((*node)->num < value)
            delete_node(&(*node)->left, value);
        else if ((*node)->num > value)
            delete_node(&(*node)->right, value);
        else
        {
    
            // TODO: deal with our children here
    
            free *node;
            *node = NULL;
        }
    }
    Last edited by iMalc; 11-28-2009 at 01:47 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User matrixx333's Avatar
    Join Date
    Mar 2009
    Posts
    67
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Binary Search Tree Delete Method
    By pobri19 in forum C# Programming
    Replies: 2
    Last Post: 09-26-2008, 09:43 AM
  3. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 04:41 PM
  4. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM
  5. Dynamic list of Objects in External File
    By TechWins in forum C++ Programming
    Replies: 3
    Last Post: 12-18-2002, 01:05 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21