Consider a binary search tree \(T\) whose keys are distinct. Show that if the right subtree of a node \(x\) in \(T\) is empty and \(x\) has a successor \(y\), then \(y\) is the lowest ancestor of \(x\) whose left child is also an ancestor of \(x\). (Recall that every node is its own ancestor.)

Because \(T\) contains \(y\), the successor to \(x\), we know that some ancestor of \(x\) (perhaps \(x\) itself) will be the left child of some parent node \(z\). We will use mathematical induction to show that \(z\) must be the successor to \(x\) and therefore \(z = y\).

In the base case, \(z\) is the parent node of \(x\), and \(x\) is \(z\)’s left child. Suppose \(z \neq y\), then there must be some \(y\) that satisfies \(x < y < z\). This implies that this \(y\) must exist in a left subtree of \(z\) and in a right subtree of \(x\), but we know \(x\) does not have a right subtree. Therefore \(z = y\), or in other words, \(z\) is the successor to \(x\).

The other possibility is that \(x\) is a right child of its parent node, say \(a_1\). Suppose this first ancestor of \(x\) is a left child of its parent node \(z\) and suppose also that \(z \neq y\). Then there must be some \(y\) that satisfies \(a_1 < y < z\). The same argument as the base case applies, but \(a_1\) has a right-subtree! Indeed, we still know that \(x\) remains the maximum value of that right subtree and so we confirm that \(z\) must be the successor of \(x\). That is, \(z = y\).

Furhtermore, suppose there are \(n\) ancestors, \(a_1, a_2, ... a_n\) between \(x\) and \(z\). \(a_1\) has right child \(x\) and parent \(a_2\). \(a_2\) has right child \(a_1\) and parent \(a_3\) and so on until \(a_n\) has parent \(z\) which it is a left child of. All of these ancestors share the same property that was described for \(a_1\): the maximum value of their right subtree is \(x\) and thus the parent node of \(a_n\) must be \(x\)’s successor. Once again, \(z = y\), and thus the claim is shown to be accurate for all possible configurations of the tree.