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\) is smaller than \(x.key\).

Suppose \(x\) is a right-child of \(y\). If we call TREE-SUCCESSOR(\(y\)), we end up seeking the minimum value of \(y\)’s right subtree which gives us \(x\). Thus \(x\) is \(y\)’s successor, or in other words, \(y.key\) is the largest key in \(T\) smaller than \(x.key\).

Next, suppose \(x\) is a left-child of \(y\). If we call TREE-PREDECESSOR(\(y\)) (see Exercise 12.2-3), we end up seeking the maximum value of \(x\)’s left subtree which gives us \(y\). Thus \(x\) is \(y\)’s predecessor, or in other words, \(y.key\) is the smallest key in \(T\) larger than \(x.key\).