Closest BST value I + II -- Leetcode

1. Closest BST value I:
Question:

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

Answer:
   public int closestValue(TreeNode root, double target) {
         int res = root.val;
         while(root!=null){
             if(Math.abs(root.val - target) < Math.abs(res - target)){
                 res = root.val;
             }
           
             if(root.val < target){
                 root = root.right;
             }else if(root.val > target){
                 root = root.left;
             }else{
                 return root.val;
             }
         }
         return res;
    }

2. Closest BST value II:
Question:

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.

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

Answer:
 2.1. BST inorder traversal using Stack + maintain K closest element in a queue! 
Time: < O(n), Space: O(k)!

   public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Queue<Integer> queue = new LinkedList<Integer>();
        if(root==null)return (List<Integer>)queue;
       
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        while(!stack.isEmpty()){
            TreeNode stackPeekNode = stack.pop();
            Integer stackPeek = stackPeekNode.val;
           
            if(queue.size() < k){
                queue.add(stackPeek);
            }else if(queue.size() == k){
                Integer quePeek = queue.peek();
                if(Math.abs(target - quePeek) > Math.abs(stackPeek - target)){
                    queue.poll();
                    queue.offer(stackPeek);
                }else{
                    //already find k closest!
                    break;
                }
            }
            //push all right subtree nodes into stack!
            TreeNode node = stackPeekNode.right;
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
        }
        return (List<Integer>)queue;
    }

2.2. Using two Stacks!: smaller element stack + larger element stack!
Time: < O(n), Space: O(k)!

public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> result = new LinkedList<Integer>();
        // populate the predecessor and successor stacks
        Stack<TreeNode> pred = new Stack<TreeNode>();
        Stack<TreeNode> succ = new Stack<TreeNode>();
        TreeNode curr = root;
        while (curr != null) {
            if (target <= curr.val) {
                succ.push(curr);
                curr = curr.left;
            } else {
                pred.push(curr);
                curr = curr.right;
            }
        }
        while (k > 0) {
            if (pred.empty() && succ.empty()) {
                break;
            } else if (pred.empty()) {
                result.add( getSuccessor(succ) );
            } else if (succ.empty()) {
                result.add( getPredecessor(pred) );
            } else if (Math.abs(target - pred.peek().val) < Math.abs(target - succ.peek().val)) {
                result.add( getPredecessor(pred) );                  
            } else {
                result.add( getSuccessor(succ) );
            }
            k--;
        }
        return result;
     }

    private int getPredecessor(Stack<TreeNode> st) {
        TreeNode popped = st.pop();
        TreeNode p = popped.left;
        while (p != null) {
            st.push(p);
            p = p.right;
        }
        return popped.val;
    }

    private int getSuccessor(Stack<TreeNode> st) {
        TreeNode popped = st.pop();
        TreeNode p = popped.right;
        while (p != null) {
            st.push(p);
            p = p.left;
        }
        return popped.val;
    }