Splay trees, a form of self-adjusting binary tree, were introduced by Sleator and Tarjan in the early 1980s. Their main use is to store ordered lists. The idea is to keep the trees reasonably well balanced through a `splay heuristic.' Sleator and Tarjan showed that if amortised rather than worst-case times are considered, splay trees are optimal. Splay trees have the advantage of simplicity: they are much easier to implement than 2-3 trees, AVL trees, or red-black trees.

What if one uses splaying during an inorder traversal of
the tree? Sleator and Tarjans' analysis guarantees
*O(n*log*(n))* overall cost. On the other hand, the cost of
ordinary inorder traversal is linear, whether or not the tree is
balanced.

We present some data which suggests that the traversal
time is *O(n)*, and demonstrate an *O(n*loglog*(n))*
upper bound. This upper bound is reached
through a rather unusual unbounded-history recurrence
and by using weaker bounds, such as the *O(n*log*(n))*
bound, along the way.