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

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.

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.

Solution:

Method 1: recursive

This is a bottom up recursive implementation.

We try to find the closest value from target from a node and its child.

And this closest value will be carried to the outer recursion which checks the node and its parent's closest value from target.

When the recursion is finished. The closest value is the global closest.



Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int closestValue(TreeNode root, double target) {
        int a = root.val;
        TreeNode child = root.val > target ? root.left : root.right;
        if (child == null) {
            return a;
        }
        int b = closestValue(child, target);
        return Math.abs(a - target) < Math.abs(b - target) ? a : b;
    }
}

Method 2: iterative

Start from the root, we try to find a path that can reach or be closer to the target.

While traversing this path, we keep an updated value that is the current closest value from target.

When we reach the bottom of the tree, the current closest value is the global closest.



Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int closestValue(TreeNode root, double target) {
        int result = root.val;
        while (root != null) {
            if (Math.abs(root.val - target) < Math.abs(result - target)) {
                result = root.val;
            }
            root = root.val > target ? root.left : root.right;
        }
        return result;
    }
}