Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting

Question

The following theorem was proven by R.E. Tarjan in 1984:

Theorem (Sequential Access Theorem). If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time spent is $O(n)$

But if we remove the smallest element one at a time, then does it imply that we sorted the element in $O(n)$ time? Of course not, because then it contradicts the following Theorem.

Any comparison sort algorithm requires $\Omega(n\lg n)$ comparisons in the worst case.

What was wrong with the way I tried to use the Sequential Access Theorem?

Answer 1

There is nothing wrong in saying that if you access the nodes of a BST (not necessarily a splay tree) in symmetric order in time $O(n)$ then the sequence of the corresponding elements is sorted.

However this alone is not enough to obtain a sorting algorithm that runs in time $O(n)$ since you're disregarding the time needed to construct the tree itself.

In fact, your observation shows that the time spent to build a BST from an unsorted set of elements must be $\Omega(n \log n)$ in the worst case.