In this paper we prove that if the nodes of an arbitrary n -node binary search tree T are splayed according to the preorder sequence of T then the total time is O ( n ) . This is a special case of the splay tree traversal conjecture of Sleator and Tarjan [1].