The COVID19 pandemic created a worldwide emergency as it is estimated that such a large number of infections are due to human-to-human transmission of the COVID19. As a necessity, there is a need to track users who came in contact with users having travel history, asymptomatic and not yet symptomatic, but they can be in the future. To solve this problem, the present work proposes a solution for contact tracing based on assisted GPS and cloud computing technologies. An application is developed to collect each user's assisted GPS coordinates once all the users install this application. This application periodically sends assisted GPS data to the cloud. To determine which devices are within the permissible limit of 5m, we perform clustering over assisted GPS coordinates and track the clusters for about t mins to allow the measure of spread. We assume that it takes around 3 or 5 mins to get the virus from an infected object. For clustering, the proposed M way like tree data structure stores the assisted GPS coordinates in degree, minute, and second format. Thus, every user is mapped to a leaf node of the tree. We split the "seconds" part of the assisted GPS location into m equal parts, which amount to d meter in latitude(longitude). Hence, two users who are within d meter range will map to the same leaf node. Thus, by mapping assisted GPS locations every t mins, we can find out how many users came in contact with a particular user for at least t mins. Our work's salient feature is that it runs in linear time O(n) for n users in the static case, i.e., when users are not moving. We also propose a variant of our solution to handle the dynamic case, that is, when users are moving. Besides, the proposed solution offers potential hotspot detection and safe-route recommendation as an additional feature, and proof of concept is presented through experiments on simulated data of 10M users.