Binary Search Tree vs Hash Table
A hash table for pure lookup, which is faster and simpler. A balanced BST when order matters: sorted iteration, range queries, or finding the nearest key to a value.
This is the same trade as HashMap against TreeMap, one level down. A hash table computes where a key belongs, so it finds it in one step and knows nothing about what is near it. A search tree compares its way down, which costs a logarithm and leaves it holding the structure that makes order queries possible.
Side by side
| Dimension | Binary Search Tree | Hash Table |
|---|---|---|
| Lookup | O(log n) balanced, O(n) if not | O(1) average |
| Sorted iteration | In-order traversal gives it free | Requires sorting, O(n log n) |
| Range query | O(log n + k) | Not supported |
| Nearest key | Supported | Not supported |
| Minimum or maximum | O(log n), walk one side | O(n), scan everything |
| Worst case | O(n) unbalanced, O(log n) if self-balancing | O(log n) with treeified buckets |
| Requires | A total ordering on keys | A good hash and equals |
When to pick each
Binary Search Tree
- Keys must come out in order, or you need the kth smallest.
- You query ranges, such as every record between two dates.
- You need predecessor and successor lookups.
Hash Table
- Membership and lookup by exact key, with nothing ordered about the access pattern.
- Keys have no natural ordering.
- Speed dominates and the constant factor matters.
Writing a plain BST and calling it O(log n). Inserting sorted data into an unbalanced BST builds a linked list of n nodes, and every operation degrades to O(n). Sorted input is common, so this is not a corner case. The O(log n) belongs to self-balancing trees such as red-black or AVL, which is what TreeMap actually is.
Questions people ask
Why is in-order traversal of a BST sorted?
Because of the invariant itself. Everything in a node's left subtree is smaller and everything in the right is larger, so visiting left, then the node, then right emits values in increasing order by construction.
How do I find the kth smallest efficiently?
An in-order traversal that stops after k values is O(h + k). If the query is frequent and the tree changes, store a subtree size on each node, which lets the search skip whole subtrees and answer in O(h).
Is a hash table ever the wrong choice for lookup?
When keys are adversarial. Deliberately colliding keys used to make lookups linear, which was a real denial of service vector. Randomised hashing and treeified buckets have largely closed it, but it is why some systems use trees where inputs are untrusted.