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.
Analysis:
Maintain a min value and update it with left and right .
Time complexity: O(logn)
Space complexity: O(1)
Code is below:
/** * 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) { // O(logn) int min = root.val; while (root != null) { min = Math.abs(target - root.val) < Math.abs(target - min) ? root.val : min; root = root.val < target ? root.right : root.left; } return min; } }