## Deletion

The procedure for deleting a given node with value "*value*" from a
binary search tree takes a pointer to *T* and the value to be deleted.
This procedure is somewhat more complex because it deals with three
different possibilities, instead of just one. If the node pointed by
*value* has no children, the conditions on lines 7, 8, and 9
are false, *temp* gets the value of *T*, and is deleted in
line 13. In other words, if the node to be deleted has no children,
we simply remove it.

If the node has only one child, either one of the two conditions in
line 7 or 8 will be true, and the statements *t=t->right* or
*t=t->left* will have the effect of "splicing out" the node by
making a link between its child and its parent. After the link is made,
the node is deleted in statement 13. The most complex situation arises
when the node has two children. In this case, the procedure slices out
the node's successor **DELETE_MIN***(T->right)* and replaces
the contents of *T* with the contents of the successor. This is
represented in the code by the statements in lines 9-13. Notice that
procedure **DELETE_MIN**, when passed the argument *(T->right)*,
finds and deletes the minimum value in the right subtree of *T*.
Since this tree contains only contains values greater than *T->value*
(and greater values cannot be anywhere else in the tree structure),
finding its minimum corresponds to finding the successor of *T*.

### Pseudo-Code

DELETE (T, value)
NODE_PTR temp;
begin
1. if (T = NIL) then print("Value not in tree")
2. else if (value < T -> value) then DELETE (T->left, value)
3. else if (value > T -> value) then DELETE (T->right,value)
4. else begin /* After finding the node then delete it */
5. alloc_node(temp);
6. temp = T;
7. if (T->left = NIL) then T = T -> right
8. else if (T->right = NIL) then T = T -> left
9. else begin
10. temp = DELETE_MIN (T->right);
11. T -> value = temp -> value;
12. end else;
13. free_node(temp);
14 end else;
15.end begin.

### Examples

The following images were created for the application using Macromedia
Director.
**Example 1:**

**Example 2:**
**Example 3:**

Previous Page

Next Page

Return to Main Page