The nearest restaurant problem
This algorithm solves the problem: return all keys that lies in [L,U].Another approach: if the order is not important, we can use pre-order traverse, and check the current node range.
NearestRestaurant.java
private static <T> BinaryTree<T> findSuccessorBST(BinaryTree<T> n) {
if (n.getRight() != null) {
// Find the smallest element in n's right subtree.
n = n.getRight();
while (n.getLeft() != null) {
n = n.getLeft();
}
return n;
}
// Find the first parent which is larger than n.
while (n.getParent() != null && n.getParent().getRight() == n) {
n = n.getParent();
}
// Return nullptr means n is the largest in this BST.
return n.getParent() != null ? n.getParent() : null;
}
public static List<BinaryTree<Integer>> rangeQueryOnBST(
BinaryTree<Integer> n, Integer L, Integer U) {
List<BinaryTree<Integer>> res = new ArrayList<>();
for (BinaryTree<Integer> it = findFirstLargerEqualK(n, L); it != null
&& it.getData().compareTo(U) <= 0; it = findSuccessorBST(it)) {
res.add(it);
}
return res;
}
private static BinaryTree<Integer> findFirstLargerEqualK(
BinaryTree<Integer> r, Integer k) {
if (r == null) {
return null;
} else if (r.getData().compareTo(k) >= 0) {
// Recursively search the left subtree for first one >= k.
BinaryTree<Integer> n = findFirstLargerEqualK(r.getLeft(), k);
return n != null ? n : r;
}
// r->data < k so search the right subtree.
return findFirstLargerEqualK(r.getRight(), k);
}
