Why use binary search trees when hash tables exist?

Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log n).

So, in a course on data structures, is the study of BST's of any value except as a historical note?

The most obvious answer is that trees can be traversed in their natural order very efficiently. If you need to visit every element of a dictionary in alphabetical order, a tree can support this directly, where a hash table cannot.

Another answer is that trees can be made immutable - where insertion and deletion only involve recreating a small number of elements back to the root, whereas hash tables can only be completely duplicated.

A related answer for mutable data is that trees can be modified concurrently, only requiring locking single nodes, whereas hash tables have to be locked as a whole if concurrent processes are to get consistent results.

StackExchange Computer Science Q#89417, answer score: 16