# O(k + logn) java solution using two queue

• When tree is balanced, this solution is O(k + log(n))

``````public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> res = new ArrayList<>();
Deque<Integer> sq = new ArrayDeque<>();
Deque<Integer> bq = new ArrayDeque<>();
traverse(root, target, k, sq, bq);
return res;
}

public void traverse(TreeNode root, double target, int k, Deque<Integer> sq, Deque<Integer> bq) {
if (root == null) {return;}
if (root.val > target) {
traverse(root.left, target, k, sq, bq);
if (bq.size() < k) {traverse(root.right, target, k, sq, bq);}
} else if (root.val < target) {
traverse(root.right, target, k, sq, bq);
if (sq.size() < k) {traverse(root.left, target, k, sq, bq);}
} else {
if (sq.size() < k) {traverse(root.left, target, k, sq, bq);}
if (bq.size() < k) {traverse(root.right, target, k, sq, bq);}
}
}

public void addResult(List<Integer> res, Deque<Integer> sq, Deque<Integer> bq, double target, int k) {
while (!sq.isEmpty() && !bq.isEmpty() && res.size() < k) {
double small = Math.abs(sq.getLast() - target);
double big = Math.abs(bq.getLast() - target);
res.add(small > big ? bq.removeLast() : sq.removeLast());
}
while (!sq.isEmpty() && res.size() < k) {