# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/272-closest-binary-search-tree-value-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.