 Solution

Use the usual bottom-up splaying operations. We prove the stronger result that at most three successful calls suffice. No insertions or deletions are needed.

If the chosen key $x$ is the minimum stored key, first perform splaying on $x$ and then on its immediate successor. The argument for consecutive keys in a binary search tree makes $x$ the left child of the successor with an empty right subtree; minimality makes its left subtree empty too. Hence $x$ is a leaf of a rooted tree. The maximum-key case is the mirror image.

Suppose $x$ is an interior key. Since at least four keys are stored, there are either two keys larger than $x$ or two smaller than $x$. In the former case choose four consecutive stored keyswhere $a$ is the predecessor of $x$, and $b,c$ are the next two successors. Perform $\mathrm{Splay}(c),\mathrm{Splay}(a),\mathrm{Splay}(b)$.

Here is a complete check of the local shapes. After the first call, $c$ is the root. After the second, $a$ is the root; every key below $a$ is in its left subtree $A$, and every key above $c$ stays in the right subtree $D$ of $c$. These outside subtrees cannot interfere with the next search. Between $a$ and $c$ there are only $x,b$. The last step of splaying on $a$ is either a zig step, leaving $c$ as its right child; a zig-zag step, with the same result; or a zig-zig step, leaving some $p\in \{x,b\}$ as its right child with $c$ immediately to the right of $p$. Consequently the possible right subtrees of $a$ are exactly among these four forms, using $k(L,R)$ for a node with its left and right subtrees:Here an unexpanded $x$ or $b$ denotes a node with no children. Each row follows by the indicated one or two tree rotations in each bottom-up step. All rows end with $x$ as the right child of $a$, with both its subtrees empty. If instead two keys below $x$ are available, reflect the construction, exchanging left and right and reversing the order of keys. This proves splaying a chosen node into a leaf for every node of every splay tree of size at least four.