# Exercise 12.2.7

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-MINIMUM`

and 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.