Editing Binary search tree (section)

===Insertion===
Operations such as insertion and deletion cause the BST representation to change dynamically. The data structure must be modified in such a way that the properties of BST continue to hold. New nodes are inserted as [[leaf nodes]] in the BST.<ref name="algo_cormen" />{{rp|294–295}} Following is an iterative implementation of the insertion operation.<ref name="algo_cormen" />{{rp|294}}
{|
|- style="vertical-align:top"
|
 1    BST-Insert(T, z)
 2      y := NIL
 3      x := T.root
 4      '''while''' x &ne; NIL '''do'''
 5        y := x
 6        '''if''' z.key < x.key '''then'''
 7          x := x.left
 8        '''else'''
 9          x := x.right
 10       '''end if'''
 11     '''repeat'''
 12     z.parent := y
 13     '''if''' y = NIL '''then'''
 14       T.root := z
 15     '''else if''' z.key < y.key '''then'''
 16       y.left := z
 17     '''else'''
 18       y.right := z
 19     '''end if'''
|}
The procedure maintains a "trailing pointer" <math>\text{y}</math> as a parent of <math>\text{x}</math>. After initialization on line 2, the '''while''' loop along lines 4-11 causes the pointers to be updated. If <math>\text{y}</math> is <math>\text{nil}</math>, the BST is empty, thus <math>\text{z}</math> is inserted as the root node of the binary search tree <math>\text{T}</math>, if it is not <math>\text{nil}</math>, insertion proceeds by comparing the keys to that of <math>\text{y}</math> on the lines 15-19 and the node is inserted accordingly.<ref name="algo_cormen" />{{rp|295}}