An alternative method of performing inorder tree walk of an $n$-node binary search tree finds the minimum element in the tree by calling
TREE-MINIMUMand then making $n-1$ calls to
TREE-SUCCESSOR. Prove that this algorithm runs in $\Theta(n)$ time.
It's a bit obvious, and it's not worth (read I'm too lazy) to create a formal
argument. We simply need to observe that we visit each node twice – once on the
way down (through
TREE-MINIMUM) and once on the way up in the
while loop of
TREE-SUCCESSOR – and we don't do extra steps inbetween.