  The (preorder) traversal conjecture states that starting with an initial
tree, the cost to search a sequence $S=(s_1,s_2,\dots,s_n) \in [n]^n$ in a
binary search tree (BST) algorithm is $O(n)$, where $S$ is obtained by a
preorder traversal of some BST. The sequence $S$ is called a preorder sequence.
  For Splay trees (candidate for dynamic optimality conjecture), the preorder
traversal holds only when the initial tree is empty (Levy and Tarjan, WADS
2019). The preorder traversal conjecture for GREEDY (candidate for dynamic
optimality conjecture) was known to be $n2^{\alpha(n)^{O(1)}}$ (Chalermsook et
al., FOCS 2015), which was recently improved to $O(n2^{\alpha(n)})$
(Chalermsook et al., SODA 2023), here $\alpha(n)$ is the inverse Ackermann
function of $n$. For a special case when the initial tree is flat, GREEDY is
known to satisfy the traversal conjecture, i.e., $O(n)$ (Chalermsook et al.,
FOCS 2015).
  In this paper, we show that for every preorder sequence $S$, there exists an
initial tree called the preorder initial tree for which GREEDY satisfies the
preorder traversal conjecture.
