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
if is_empty(T):
T.root = x
else:
c = T.root // c is the current node.
p = c.parent // p is the parent of c
while is_not_null(c):
p = c
if x < c:
c = c.left
else:
c = c.right
if x < p:
p.left = x
else:
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 c
, i.e. 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 if
-else
block after the while loop, we can also set the parent of x
to be p
.
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.