Inorder Successor in Binary Search Tree

Question

This is the problem that I have to solve:

given a node in a binary search tree, find the node with the smallest key that is greater than the key of the given node..

The algorithm that is often given is this one:

bst_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x = y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

(you can find further explanations of the problem here.)

Now, I was wondering if this can be another solution:

bst_successor(x)
    {
            if(x == NULL)
                    return NULL;
            if(x.right != NULL)
                    return abr_min(x.right)
            y = x.p;
            while(y != NULL && y.key < x.key)
            {
                    y = y.p;
            }
            return y;
    }

Answer 1

Your code is correct if the key of one node is never equal to the key of a different node.

Otherwise, you code fails to return the correct inorder-successor of the node at the bottom of the following graph.