# Simple C++ solution with priority queue

• There are many ways to solve this problem. Heap is one of them.

``````void dfs(TreeNode* root, priority_queue<pair<double, int>>& pq, double target, int k) {
if(!root) return;

pq.push(make_pair(fabs(target - double(root->val)), root->val));

if(pq.size() > k)
pq.pop();

dfs(root->left, pq, target, k);
dfs(root->right, pq, target, k);
}

vector<int> closestKValues(TreeNode* root, double target, int k) {
priority_queue<pair<double, int>> pq;
vector<int> result;

dfs(root, pq, target, k);
while(!pq.empty()) {
result.push_back(pq.top().second);
pq.pop();
}

return result;
}``````

• Great code, very nice design of the `pair<double, int>` :-)

• Why are you popping front in these lines if(pq.size() > k) pq.pop();, will it no delete the closest value. as it will be at top of the pq?

• I think priority queue does not give less than O(n) time, since it visits all the node in the BST. To do it O(n) time, a simple in order traversal is more efficient. However, to achieve less than O(n) time we need to use the method following the hint.

• What is the time complexity of this method? O(N) or O(NlogN)? Thanks

• It is O(nlogn). Slower than other solutions, but easy to make.

• O(nlogk), didn't know pair has a default comparator :)

• Code is pretty neat, yet it's O(Nlogk) which is worse than O(N) which can also be done with neat traverse code. However, it doesn't meet the better than O(N) request.

• @jaewoo Could you please tell me why the max-heap is used instead of min-heap? The problem seems to look for closest value, which means it is looking for k smallest difference between node value and target.

• This solution is suitable if the given input is a non-BST or any BT/array. Its complexity is O(N * logK). A more appropriate solution would leverage the benefits of BST while solving this problem.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.