Binary search tree: insert

TREE-INSERT(T, z)

y = Null

x = root(T)

while x ≠ NULL

y = x

if key[z] < key[x]

then x = left[x]

then x = right[x]

p[z] = y

if y = NULL

then root[T] = z //Tree was empty

else if key[z] < key[y]

then left[y] = z

else right[y] = z