Greedy on preorder is linear for preorder initial tree

Abstract

The (preorder) traversal conjecture states that starting with an initial tree, the cost to search a sequence S=(s1,s2,…,sn)∈[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α(n)O(1) (Chalermsook et al., FOCS 2015), which was recently improved to O(n2α(n)) (Chalermsook et al., SODA 2023), here α(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.