Binary search tree: remove

TREE-DELETE(T,z)

if left[z] = NULL or right[z] = NULL

then y = z

else y = TREE-SUCCESSOR(z)

if left[y] ≠ NULL

then x = left[y]

else x = right[y]

if x ≠ NULL

then p[x] = p [y]

if p[y] = NULL

then root[T] = x

else if y = left[p[y]]

then left[p[y]] = x

else right[p[y]] = x

if y ≠ z

then key[z] = key[y]

copy y's satellite data into z

return y