On Finding the Height of a Binary Search Tree

The preorder, inorder and postorder traversals of binary trees are standard topics in Data Structures courses. A common example (or test question) which uses postorder traversal is finding the height of a randomly formed binary search tree (to verify experimentally that it is indeed O(log n)). The natural postorder implementation gives a linear algorithm, but frequently students manage, sometimes unintentionally, to add a third recursive call to the computation, resulting in an apparently drastic increase in running time. It is obvious that the worst case running time increases from linear to exponential, but the results on the average case running time are not as immediate