Lintcode 900. Closest Binary Search Tree Value

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

Example

Example1

Input: root = {5,4,9,2,#,8,10} and target = 6.124780
Output: 5

Example2

Input: root = {3,2,4,1} and target = 4.142857
Output: 4

Notice

• 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.

Code (Java):

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @return: the value in the BST that is closest to the target
     */
    public int closestValue(TreeNode root, double target) {
        // write your code here
        int floor = getFloor(root, target);
        int ceil = getCeil(root, target);
        
        if (floor == Integer.MIN_VALUE) {
            return ceil;
        }
        
        if (ceil == Integer.MIN_VALUE) {
            return floor;
        }
        
        if (Math.abs(floor - target) < Math.abs(ceil - target)) {
            return floor;
        } else {
            return ceil;
        }
    }
    
    private int getFloor(TreeNode root, double target) {
        TreeNode p = root;
        TreeNode parent = null;
        
        while (p != null) {
            if ((double)p.val == target) {
                return p.val;
            }
            
            if (p.val < target) {
                parent = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        
        if (parent == null) {
            return Integer.MIN_VALUE;
        }
        
        return parent.val;
    }
    
    private int getCeil(TreeNode root, double target) {
        TreeNode p = root;
        TreeNode parent = null;
        
        while (p != null) {
            if ((double)p.val == target) {
                return p.val;
            }
            
            if (p.val < target) {
                p = p.right;
            } else {
                parent = p;
                p = p.left;
            }
        }
        
        if (parent == null) {
            return Integer.MIN_VALUE;
        }
        
        return parent.val;
    }
}