# 272 Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, findkvalues 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)?

**The Idea:** Use a priority queue to maintain the top k closest values (similarly to the k closest distances problem). There are a few tricks I did to get this to work with a priority queue. Since by default the priority queue will compare the first element of a tuple, our main comparator will be defined as `distance(target, root.val)`. Secondly because priority queue defaults as a min heap, and we need to treat it as a max heap, and inverse the values with (-), and then reverse the logic we would have defined for a min heap. Secondly, because there may be duplicates in our heap (that are equidistant to the target), we need a second parameter in our tuple that will resolve this arbitrarily. I resolved this by passing in a unique counter id for each node.

**Complexity:** O(Nlog(k)) time since we iterate through all the elements in the tree, processing each element will take time proportional to the number of elements in the pq. O(K) space.

```python
from queue import PriorityQueue


class Solution:
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """

        fix_same_dist_conflict = [0]
        pq = PriorityQueue()
        def pre_order_dfs(root):
            if root:
                # if the current distance exceeds the current
                # smallest maximum of the pq (inverse logic)
                cur_dist = -abs(target - root.val)
                if pq.qsize() == k and pq.queue[0][0] < cur_dist:
                    pq.get()
                    pq.put((cur_dist, fix_same_dist_conflict[0], root))
                elif pq.qsize() < k:
                    pq.put((cur_dist, fix_same_dist_conflict[0], root))
                fix_same_dist_conflict[0] += 1
                pre_order_dfs(root.left)
                pre_order_dfs(root.right)

        pre_order_dfs(root)
        solution = []
        while not pq.empty():
            solution.append(pq.get()[2].val)
        return solution
```