Closest Binary search tree I && II

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target.

The first one is quite easy. Using binary search. The closest value should either be the root value or one of its children. Recursively get the closest value from the children and compare it with the root value.

public int closestValue(TreeNode root, double target) {
        if (root == null) {
            return -1;
        }
        return getClosestValue(root, target);
    }

    private int getClosestValue(TreeNode root, double target) {
        TreeNode kid = target < root.val ? root.left : root.right;
        if (kid == null) {
            return root.val;
        }
        int closest = getClosestValue(kid, target);
        double difference = Math.abs(root.val - target) - Math.abs(kid.val - target);
        return difference > 0 ? closest : root.val;
    }

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note: Given target value is a floating point. You may assume k is always valid, that is: k ≤ total nodes. You are guaranteed to have only one unique set of k values in the BST that are closest to the target. Follow up: Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

Consider implement these two helper functions: getPredecessor(N), which returns the next smaller node to N. getSuccessor(N), which returns the next larger node to N.

Using a priority queue. Recursively do an in order traversal and put nodes in the queue. If the size of the queue exceeds k, pull out the node with the largest difference.

public List<integer> closestKValues(TreeNode root, double target, int k) {
        List<integer> rst = new ArrayList<>();
        if (root == null) {
            return rst;
        }
        PriorityQueue<integer> queue = new PriorityQueue<>(k, new Comparator<integer>() {
            @Override public int compare(Integer o1, Integer o2) {
                double difference = Math.abs(o1.doubleValue() - target) - Math.abs(o2.doubleValue() - target);
                if (difference > 0) {
                    return -1;
                } else if (difference < 0) {
                    return 1;
                } else {
                    return 0;
                }
            }
        });
        getKValues(root, target, k, queue);
        while (!queue.isEmpty()) {
            rst.add(queue.poll());
        }
        return rst;
    }

    private void getKValues(TreeNode root, double target, int k, PriorityQueue queue) {
        if (root == null) {
            return;
        }
        getKValues(root.left, target, k, queue);
        queue.add(root.val);
        if (queue.size() > k) {
            queue.poll();
        }
        getKValues(root.right, target, k, queue);
    }