Exercise 12.2.9

Let $T$ be a binary search tree whose keys are distinct, let $x$ be a leaf node, and let $y$ be its parent. Show that $y.key$ is either the smallest key in $T$ larger than $x.key$ or the largest key in $T$ smaller than $x.key$.

We explored this already in the previous few exercises.

Let's consider $y.left = x$. $y.right$ will not contain elements larger than $x.key$ but smaller than $y.key$ (binary search tree property). $y$'s parents will be either left of it (which means their key is smaller than $x.key$, as are those of their left subtree) or right of it (in which case their key would be bigger than $y.key$.

If $y.right = x$ similar logic applies.