Insertion Into Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has the following properties: 

• The left subtree of a node contains only nodes with keys less than the node’s key. 
• The right subtree of a node contains only nodes with keys greater than the node’s key. 
• The left and right subtree each must also be a binary search tree. 
• There must be no duplicate nodes.

Binary Search Tree in Data Structures

Algorithm:

INSBST (INFO, LEFT, RIGHT, ROOT, AVAIL, ITEM, LOC, PAR)

A binary search tree T is in memory and an ITEM of information is given. This algorithm finds the location LOC of ITEM in T or adds ITEM as a new node in T at location LOC.

Step I: Call FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR)

Step II: If LOC != NULL, then: Exit.
[Element already in tree.]

Step III: [Copy ITEM into new node in AVAIL list.]
a) If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
b) [Take free node from AVAIL list.]
(i) Set NEW := AVAIL, and AVAIL := LINK[AVAIL].
(ii) Set INFO[NEW] := ITEM.
c) Set LOC := NEW, LEFT[NEW] := NULL, and RIGHT[NEW] := NULL.

Step IV: [Add ITEM to the tree.]
If PAR := NULL, then: [Tree empty.]
Set ROOT := LOC.
Else if:
ITEM < INFO[PAR], then: [ITEM is added as a left child.]
Set LEFT[PAR] := LOC.
Else: [ITEM is added as a right child.]
Set RIGHT[PAR] := LOC.
[End of If structure.]

Step V: Exit.