  Let $T$ be a binary search tree. We prove two results about the behavior of
the Splay algorithm (Sleator and Tarjan 1985). Our first result is that
inserting keys into an empty binary search tree via splaying in the order of
either $T$'s preorder or $T$'s postorder takes linear time. Our proof uses the
fact that preorders and postorders are pattern-avoiding: i.e. they contain no
subsequences that are order-isomorphic to $(2,3,1)$ and $(3,1,2)$,
respectively. Pattern-avoidance implies certain constraints on the manner in
which items are inserted. We exploit this structure with a simple potential
function that counts inserted nodes lying on access paths to uninserted nodes.
Our methods can likely be extended to permutations that avoid more general
patterns. Second, if $T'$ is any other binary search tree with the same keys as
$T$ and $T$ is weight-balanced (Nievergelt and Reingold 1973), then splaying
$T$'s preorder sequence or $T$'s postorder sequence starting from $T'$ takes
linear time. To prove this, we demonstrate that preorders and postorders of
balanced search trees do not contain many large "jumps" in symmetric order, and
exploit this fact by using the dynamic finger theorem (Cole et al. 2000). Both
of our results provide further evidence in favor of the elusive "dynamic
optimality conjecture."
