Deleting a Node from a Binary Search Tree

As when deleting a node from a normal linked-list, there are two problems to solve when deleting a node from binary search tree. The first problem is to find the node to delete, and the second problem is to rearrange pointers. For this we use two seperate functions. I happened to name them DeleteItem and DeleteNode (it is a bad idea to use "delete" which can be a reserved word). DeleteItem will find the node and DeleteNode will move the pointers around.

To find the correct node, we simply search left or right. When we find the correct node, we call DeleteNode. 

void DeleteItem (treenode *&tree, int item)
{
   if (tree == NULL) 	// empty tree or not in the tree
	return;

   if (item < tree->info)          // Go Left
     DeleteItem (tree->left, item);
   else if (item > tree->info)     // Go Right
     DeleteItem (tree->right, item);
   else                            // This is It
     DeleteNode (tree);
}

Moving the pointers around is either really easy or really hard, depending on the structure of the tree. If there is no left branch, then we can just move the pointer to the right. For example: 

    10
     \
     20
     / \ 
    25 30
To remove the 10, since 10 does not have a left child, we simply move the root pointer from 10 to the right child 20. The same works for trees with no right side.

The difficult deletion case, is where there is both a left sub-tree and a right sub-tree. Then are several ways to solve this situation. One way is to find the right-most node of the left sub-tree (the biggest of the small values) and move that value to the root. After moving the value, there will be a duplicate item that now has to be deleted. 

void DeleteNode (treenode *&tree)
{
  node *temp;
  
  temp = tree;
  if (tree->left == NULL)		// no left child is easy
    {
	tree = tree->right;
	delete temp;
    }
  else if (tree->right == NULL)	// no right is also easy
    {
	tree = tree->left;
	delete temp;
    }
  else                           // both left & right exist
    {
     temp = tree->left;          // find right-most node of left sub-tree
     while (temp->right != NULL)
       temp = temp->right;
     tree->info = temp->info;    // move just that value to root
     DeleteItem (tree->left, temp->info);   // delete duplicate data
    }
}