Question
You are given information about hotels in a country/city. X and Y coordinates of each hotel are known. You need to suggest the list of nearest hotels to a user who is querying from a particular point (X and Y coordinates of the user are given). Distance is calculated as the straight line distance between the user and the hotel coordinates.
Solution
Build a 2-D Tree (by using Binary Tree).
First find the root, then divide the rest of nodes by left-side and right-side. Then, divide by up-side and down-side.
There’s a very good example video here, which talked about how to construct a 2-D tree.
After this preprocessing, the search for nearest hotels in about O(lgn). However, if we were to return a list of nearest nodes, I’ve got no idea.