Write the TREE-PREDECESSOR procedure.

TREE-PREDECESSOR(x)

1 if x.left ≠ NIL:

2     return TREE-MAXIMUM(x.left)

3 y = x.parent

4 while y ≠ NIL and x == y.left:

5     x = y

6     y = y.parent

7 return y