CloestBinarySearchTreeValueIIPreorder.java

public List<Integer> closestKValuesUsingPreOrder(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        // PQ by default is ascending order using the element's natural order, so by default, it's a min heap
        Queue<Node> pq = new PriorityQueue<>(); // max heap

        this.preOrderTraversal(root, target, pq, k);

        for (Node n : pq) {
            res.add(n.val);
        }

        return res;
    }

    // This method uses a pre-order traversal that traverses the entire tree, O(N*lgK), not optimal
    public void preOrderTraversal(TreeNode root, double target, Queue<Node> pq, int k) {
        if (root == null) {
            return;
        }

        if (pq.size() < k) {
            pq.add(new Node(root.val, Math.abs(target - root.val)));
        } else {
            double diff = Math.abs(target - root.val);
            if (diff < pq.peek().diff) {
                pq.poll();
                pq.add(new Node(root.val, diff));
            }
        }

        this.preOrderTraversal(root.left, target, pq, k);
        this.preOrderTraversal(root.right, target, pq, k);
    }

    public class Node implements Comparable {
        public int val;
        public double diff;

        public Node(int val, double diff) {
            this.val = val;
            this.diff = diff;
        }

        // Want to build a max heap
        public int compareTo(Object o) {
            Node n = (Node)o;
            return (int)(n.diff - this.diff);
        }
    }