An alternative method of performing an 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.

By its nature an inorder tree walk will traverse the entire binary search tree, so we know our lower bound must be \(\Omega(n)\).

This particular approach will visit some nodes more than once but will never travel the same edge more than twice. Consider the two possible ‘movements’ this traversal can make:

1. The minimum movement: Any time a node has an untraversed right subtree (or at the start of this procedure) we move along the left-most border edges to reach the subtree’s minimum value.
2. The return movement: A node with no right subtree produces this movement wherein we step to the node’s parent and repeat until we have stepped to the parent of a left-child.

These two movements represent a process of traversing every node in the tree by crossing most edges twice (The edge connected to the tree’s maximum leaf node value is only traversed once). Since an \(n\)-node binary search tree has \(n - 1\) edges this gives our \(n - 1\) calls to TREE-SUCCESSOR an upper bound of \(O(n)\).

These two bounds combine to give us a \(\Theta(n)\) runtime for this alternative inorder tree walk method.