# O(n) one pass solution with one queue (Recursion)

• The idea is very straightforward. I use a queue and inorder traverse the whole tree so that we can meet element in sorted order.

• If queue.size() < k. Just put element into queue.

• If queue.size() >= k. We compare root.val with q.peek() and dequeue when |target - q.peek()| > |target - q.peek()|. We can make sure all the elements are closer to target since we meet elements in sorted order.

public class Solution {

``````  public List<Integer> closestKValues(TreeNode root, double target, int k) {
inorderTraverse(root, q, target, k);
return (List<Integer>)q;
}

public void inorderTraverse(TreeNode root, Queue<Integer> q, double target, int k) {
if (root == null) return;
inorderTraverse(root.left, q, target, k);
if (q.size() < k) {
q.offer(root.val);
} else {
double diff1 = Math.abs(q.peek() - target);
double diff2 = Math.abs(root.val - target);
if (diff1 > diff2) {
q.poll();
q.offer(root.val);
}
}
inorderTraverse(root.right, q, target, k);
}
``````

}

• @xctom I came up with something similar; too bad it's O(NlgN) in the worst case -_- :

``````    public List<Integer> closestKValues(TreeNode root, double target, int k) {
if (root == null) return new ArrayList<>();

PriorityQueue<Integer> pq = new PriorityQueue<>(k,
(a, b) -> Double.compare(Math.abs(a - target), Math.abs(b - target)));

Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();