CloestBinarySearchTreeValueIIUseTwoStacks.java

    /**
        this method is also worst case O(N), however, if BST is balanced, this would be O(K + lgN)
     */
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();

        Stack<Integer> predecessors = new Stack<>();
        Stack<Integer> successors = new Stack<>();

        this.traverseTreeInorder(root, target, predecessors);
        this.traverseTreeReverseInorder(root, target, successors);

        while (k > 0) {
            if (predecessors.empty()) {
                res.add(successors.pop());
            } else if (successors.empty()) {
                res.add(predecessors.pop());
            } else if (Math.abs(predecessors.peek() - target) < Math.abs(successors.peek() - target)) {
                res.add(predecessors.pop());
            } else {
                res.add(successors.pop());
            }

            k--;
        }

        return res;
    }

    private void traverseTreeInorder(TreeNode node, double target, Stack<Integer> predecessor) {
        if (node == null) {
            return;
        }

        this.traverseTreeInorder(node.left, target, predecessor);

        // have to exclude at least once from either methods traverseTreeInorder or traverseTreeReverseInorder to avoid
        // duplicates
        if (node.val >= target) {
            return;
        }

        predecessor.push(node.val);

        this.traverseTreeInorder(node.right, target, predecessor);

    }

    private void traverseTreeReverseInorder(TreeNode node, double target, Stack<Integer> successor) {
        if (node == null) {
            return;
        }

        this.traverseTreeReverseInorder(node.right, target, successor);

        if (node.val < target) {
            return;
        }

        successor.push(node.val);

        this.traverseTreeReverseInorder(node.left, target, successor);
    }