# 272. (Locked)Closest Binary Search Tree Value II

Difficulty: Hard

Frequency: N/A

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.

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

1. Consider implement these two helper functions:
1. `getPredecessor(N)`, which returns the next smaller node to N.
2. `getSuccessor(N)`, which returns the next larger node to N.
2. Try to assume that each node has a parent pointer, it makes the problem much easier.
3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
4. You would need two stacks to track the path in finding predecessor and successor node separately.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
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;
}
void dfs(TreeNode* node, priority_queue<pair<double, int>>& pq, double target, int k) {
if (!node) return;
pq.push(make_pair(abs(target - (double)node->val), node->val));
if (pq.size() > k) pq.pop();
dfs(node->left, pq, target, k);
dfs(node->right, pq, target, k);
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: