Maybe this is not the "proof" you're looking for, but here's an attempt to convince anyone that $X$ will be inserted in the binary-search tree (BST) as $Y$'s right child.
The "proof" relies on the binary-search tree property and on the definition and correctness of the "insertion" and "successor" functions of a BST.
You start with the definition of a successor of a node $y$ in a BST:
If a node $y$ has a right subtree, then the successor of $y$, call it $z$, is the minimum node of that right subtree
Otherwise, it is the first ancestor of $y$, lets call it $z$, such that $y$ falls in the left subtree of $z$.
If $z$ is not found in the previous two points, then $z$ does not exist, which implies that $y$ is the greatest element in the BST.
However, we also need to look at the pseudocode of the insertion function.
function insertion(T, x):
// T is the binary-search tree
// x is the element which needs to inserted in T
T.root = x
c = T.root // c is the current node.
p = c.parent // p is the parent of c
p = c
if x < c:
c = c.left
c = c.right
if x < p:
p.left = x
p.right = x
x.parent = p
Since, in your case, we know that $T$ is not empty, then the
else block will be always executed in any run of the
insertion algorithm. In the
while loop, we go down the tree, until we find a node that is null (and
c represents this
null node). However, note that we keep track of the parent of that null node
p. We know that
p is going to be the parent of
x, but we still do not know if
x needs to be the left or right child of
p, given that
x could either be respectively smaller or greater than
p. Once that is determined, using the
else block after the while loop, we can also set the parent of
x to be
I will not prove that this insertion algorithm is correct, that is, it maintains the BST property. We assume it is correct. Here's the "proof" then.
We know that $Y$ does not have a right child, but it has a successor. Therefore, the successor must be the first ancestor of $Y$, call it $Z$, such that $Y$ falls in the left subtree of $Z$. We know that $Z$ exists (by assumption). If you insert $X$ in the binary-search tree $T$, such that $Y < X < Z$, then $X$ will be the next successor of $Y$ (by definition).
Given that $Y < X < Z$, at some point during the
insertion algorithm, the condition
x < c is false (because $X > Y$), where
c is $Y$ and
x is $X$. This must be true because there is no node between $Y$ and $X$ in the tree. Hence, in that case, $X$ will consequently be inserted in the tree as $Y$'s right child.