PROCEDURE TREE_DELETE(HEAD,X)
[Given a binary tree whose root node address is given by the pointer value HEAD and the information value (X) of the node marked for deletion, this procedure deletes the node whose information field is equal to X].

1. [Initialize]

If LPTR(HEAD) != NULL
then CUR <-- LPTR(HEAD)
PARENT <-- HEAD
else
write (“Empty tree”)
return.

2. [Search the node which is marked for deletion]

FOUND <-- false
Repeat while not FOUND and CUR != NULL
if X = DATA(CUR)
FOUND <-- true
else if X > DATA(CUR)
then (branch right)
PARENT <-- CUR
CUR <-- RPTR(CUR)
D <-- ‘R’
else
then (branch left)
PARENT <-- CUR
CUR <-- LPTR(CUR)
D <-- ‘L’
if FOUND = false
then write (“Node not found”)
return.

3. [Performing the deletion]

If LPTR(CUR) = NULL
Q <-- RPTR(CUR)
else if RPTR(CUR) = NULL
Q <-- LPTR(CUR)
else (check right child is inorder successor or not)
SUC <-- RPTR(CUR)
if LPTR(SUC) = NULL
then Q <-- SUC
else
repeat while LPTR(SUC) != NULL
PRED <-- SUC
SUC <-- LPTR(PRED)
Q <-- SUC
LPTR(PRED) <-- RPTR(SUC)
LPTR(Q) <-- LPTR(CUR)
RPTR(Q) <-- RPTR(CUR)
if D = ‘L’
LPTR(PARENT) <-- Q
else
RPTR(PARENT) <-- Q.

4. [FINISH]
return.