Question

What are the advantages of binary search trees over hash tables?

Answer

1. More memory-efficient. (They do not reserve more memory than they need to)

   For instance, if a hash function has a range R(h) = 0…100, then you need to allocate an array of 100 (pointers-to) elements, even if you are just hashing 20 elements.

2. Inorder traverse.

3. Collision might hamper HashMap’s performance.

4. Resizing issue

   When the hash table pressure grows too much, you often tend to enlargen and reallocate the hash table. The BST has simpler behavior here and does not tend to suddenly allocate a lot of data and do a rehashing operation.

5. Binary search tree do range searches efficiently.

One more thing

Trees tend to be the ultimate average data structure. They can act as lists, can easily be split for parallel operation, have fast removal, insertion and lookup on the order of O(lgn). They do nothing particularly well, but they don’t have any excessively bad behavior either.