Problem:
Given a binary search tree and a target value, find k values (k < total nodes) in the BST that are closest to the target.
For example:
given the following tree and target = 4, and k = 2
5
/ \
2 9
/ \
1 3
Output: [3,5]
Solution:
One way to solve this is to convert the tree into an array, then use a priority queue to find the top k. Notice the priority queue element needs 2 fields -- the node value, the delta between the node value and target. The delta is used by the comparator.
We can avoid converting the tree into an array, we just need to visit all the node once, we can use tree traversal for that purpose.
import java.util.*;
class Solution {
public static void main(String...args) {
Node root = new Node(5,
new Node(2, new Node(1, null, null), new Node(3, null, null)),
new Node(1, null, null)
);
PriorityQueue<int[]> pq = new PriorityQueue<>((i, j) -> j[1] - i[1]);
int target = 4;
int k = 2;
closest(root,target, k, pq);
while(!pq.isEmpty()){
int[] x = pq.poll();
System.out.print(x[0] + " ");
}
System.out.println();
}
private static void closest(Node root, int target, int k, PriorityQueue<int[]> pq) {
if(root == null) return;
closest(root.left, target, k, pq);
pq.offer(new int[]{root.value, Math.abs(root.value - target)});
if(pq.size() > k)
pq.poll();
closest(root.right, target, k, pq);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
class Solution {
public static void main(String...args) {
Node root = new Node(5,
new Node(2, new Node(1, null, null), new Node(3, null, null)),
new Node(1, null, null)
);
PriorityQueue<int[]> pq = new PriorityQueue<>((i, j) -> j[1] - i[1]);
int target = 4;
int k = 2;
closest(root,target, k, pq);
while(!pq.isEmpty()){
int[] x = pq.poll();
System.out.print(x[0] + " ");
}
System.out.println();
}
private static void closest(Node root, int target, int k, PriorityQueue<int[]> pq) {
if(root == null) return;
closest(root.left, target, k, pq);
pq.offer(new int[]{root.value, Math.abs(root.value - target)});
if(pq.size() > k)
pq.poll();
closest(root.right, target, k, pq);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
The time complexity is O(N + klogk), the space complexity is O(logN + k)
