# BST representation of Hash Tables

I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables.

I googled a lot for BST Representation of Hash Table. Code in C++ but didn't find any link or example. Can someone help me with the implementation. I'm really confused how to represend Key-Value pairs on BST. And what if there are collisions etc.

All, I found was comparison b/w BST and HasTables:

What the author means by implementing a HashTable as a BST is simply implementing a BST with $insert(), \space delete() \space and \space search()$ with slight modifications

1. The node of the BST would have the following structure. $Node \space := (Key,Value)$.
2. Insert a key-value pair by performing comparisons on the keys of two different pairs.
3. Avoids nodes with redundant keys i.e. before insertion, if a node in the BST with the same key value exists, do not insert it. Else if no node with the same key exists, insert the key-value pair.
4. No change in delete function.
5. Search returns $null$ if no node's key matches, else return the value associated with the key which was searched.

Then use these functions assuming that these perform the corresponding operations on a HashTable.
Using a self-balancing BST would give $O(log\space n)$ time complexity for all the three functions defined above. And iterating through all the key-value pairs would simply mean doing an in-order traversal of the BST.

• Actually, the author says about ability to iterate over keys IN ORDER, so in-order traversal is that she means – Bulat Sep 16 '18 at 20:17
• @Bulat Oh right, thanks for the correction. I guess I glanced over the last part of the sentence. – RandomPerfectHashFunction Sep 16 '18 at 20:19