Algorithm to Delete Node from Binary Search Tree

To delete a node following possibilities might be arise

Node id a terminal node

Node have only one child

Node having 2 children.

DEL (INFO, LEFT, RIGT, ROOT, AVAIL, ITEM)

A binary search tree T is in memory and an ITEM of information is given. This algorithm deletes ITEM from the tree.

1.  [Find the locations of ITEM and its parent]

Call FINDS (INFO, RIGHT, ROOT, ITEM, LOC, and PAR).

2.  [ITEM in tree?]

if LOC=NULL, then write : ITEM not in tree, and Exit.

3.  [Delete node containing ITEM.]

if RIGHT[LOC] != NULL and LEFT[LOC] !=NULL then:

 Call CASEB(INFO,LEFT,RIGHT,ROOT,LOC,PAR).

Else:

 Call CASEA (INFO,LEFT,RIGHT,ROOT,LOC,PAR).

[End of if structure.]

4.  [Return deleted node to AVAIL list.]

Set LEFT[LOC]:=AVAIL and AVAIL:=LOC.

5.  Exit.

CASEB(INFO,LEFT,RIGHT,ROOT,LOC,PAR)