Google Interview Question
Software Engineer / DevelopersI am not sure what you mean by PREDECESSOR AND SUCCESSOR. In BST, Is relationship among data like parent and child important in the aspect of data itself?
However, I agree with the opinion the BST have two functions, Index + storage. I think BST is better when there is not efficient hashtable because hash table and the function complex is + alpha on the process.
BST is sorted.
Linked list is ordered( elements r adde d in a specific order of arrival.
hash table is unordered and unsorted.
Use a llist if u need to store data of stops a bus or a train visits.
A hashT if you want to store contents of a dictionary,where u need a quick access to a value.
Use a BST if you Need sort+ a good search time.
I cannot think of a practical use where to use BST.but I guess it's variations ve sum practical applications.
In my opinion, the edges BST have over Hash is its sorted attribute .
1, you could easily get Max, Min from BST,
2, Traversal data in order
3, lookup data in a certain range
etc.
Any way, if the operations you need have some thing to do with order , BST is better. Hash have NO order info saved , you could only lookup one by one ( of course for a single lookup , Hash could kick BST's ass with its super speed ) ....
Hashtable is for dictionary operations like INSERT, DELETE, SEARCH. whereas Search trees can be used for dynamic-set operations including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT and DELETE. Thus, a search tree can be used both as a dictionary and as a priority queue.
- topgun.in January 16, 2010