This paper presents an efficient branch-and-bound R-tree traversal algorithm for finding the nearest neighbor (NN) object to a given point and generalizes it to find the k nearest neighbors. The algorithm uses two metrics, MINDIST and MINMAXDIST, to order and prune the search tree. MINDIST provides an optimistic estimate of the distance from the query point to the MBR or data object, while MINMAXDIST provides a pessimistic estimate. These metrics help in efficiently pruning the search space and reducing the number of nodes visited. The algorithm is tested on both synthetic and real-world data, showing good performance and scalability. The results indicate that MINDIST is more effective for spatially sorted data, while MINMAXDIST is more pessimistic but still useful for pruning. The algorithm is applicable to various spatial data structures, not just R-trees. The experiments demonstrate that the algorithm scales well with the number of nearest neighbors requested and the size of the data set. The paper concludes that the proposed algorithm and metrics are valuable tools for efficiently directing and pruning the nearest neighbor search in spatial databases.This paper presents an efficient branch-and-bound R-tree traversal algorithm for finding the nearest neighbor (NN) object to a given point and generalizes it to find the k nearest neighbors. The algorithm uses two metrics, MINDIST and MINMAXDIST, to order and prune the search tree. MINDIST provides an optimistic estimate of the distance from the query point to the MBR or data object, while MINMAXDIST provides a pessimistic estimate. These metrics help in efficiently pruning the search space and reducing the number of nodes visited. The algorithm is tested on both synthetic and real-world data, showing good performance and scalability. The results indicate that MINDIST is more effective for spatially sorted data, while MINMAXDIST is more pessimistic but still useful for pruning. The algorithm is applicable to various spatial data structures, not just R-trees. The experiments demonstrate that the algorithm scales well with the number of nearest neighbors requested and the size of the data set. The paper concludes that the proposed algorithm and metrics are valuable tools for efficiently directing and pruning the nearest neighbor search in spatial databases.