PROCEDURE TREE_INSERT(HEAD,X,Y)
[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 insertion, this procedure inserts the node (Y) 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. [Traverse to the destination node]

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 insertion]

If LPTR(CUR) = NULL
DATA(LPTR(CUR)) <-- Y
else if RPTR(CUR) = NULL
DATA(RPTR(CUR)) <-- Y
else
TEMP <-- LPTR(CUR)
LPTR(CUR) <-- NEW
LPTR(NEW) <-- TEMP.

4. [FINISH]
return.