CLRS Exercise 12.2-3

12.2-3
Write the TREE-PREDECESSOR procedure.

If a node x has a left child, its predecessor is the rightmost node of left sub-tree. Otherwise, the predecessor is the lowest ancestor of x whose right child is an ancestor of x.

TREE-PREDECESSOR(x)
        if x.left != NIL
                return TREE-MAXIMUM(x->left)
        p = x.p
        while p != NIL and x != p.right
                x = p
                p = p.p
        return p