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)